[백준/BOJ] 백준 16118번 : 달빛 여우

https://www.acmicpc.net/problem/16118

16118번: 달빛 여우

다익스트라를 이용하여 문제를 해결하였는데, 늑대의 경우 [빠르게 갈 때인지 느리게 갈 때인지(1:빠르게, 0:느리게)][위치]를 고려하여 문제를 해결했다. 그래서 늑대의 경우 우선순위 큐를 priority_queue<pair<pair<long long, int>, int>> pq; //((-비용,위치),빠르게 갈 때인지 느리게 갈 때인지(1:빠르게, 0:느리게)) 로 만들어서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

int n, m;
vector<pair<long long, int>> adj[4001];
vector<long long> fox_result(4001, 10000000001);
vector<vector<long long>> wolf_result(2, vector<long long>(4001, 10000000001)); //[빠르게 갈때인지 느리게 갈때인지(1:빠르게, 0:느리게)][위치]
int result = 0;

void FoxSolve()
{
	priority_queue<pair<long long, int>> pq; //(-비용,위치)

	fox_result[1] = 0;
	pq.push(make_pair(-0, 1));

	while (!pq.empty())
	{
		long long here_cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();

		if (fox_result[here] < here_cost)
			continue;

		long long there_cost;
		int there;

		for (int i = 0; i < adj[here].size(); i++)
		{
			there_cost = here_cost + (long long)(adj[here][i].first * 2);
			there = adj[here][i].second;

			if (there_cost < fox_result[there])
			{
				fox_result[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
			}

		}

	}
}

void WolfSolve()
{
	priority_queue<pair<pair<long long, int>, int>> pq; //((-비용,위치),빠르게 갈때인지 느리게 갈때인지(1:빠르게, 0:느리게))

	wolf_result[1][1] = 0;
	pq.push(make_pair(make_pair(-0, 1), 1));

	while (!pq.empty())
	{
		long long here_cost = -pq.top().first.first;
		int here = pq.top().first.second;
		int here_fast = pq.top().second;
		pq.pop();

		if (wolf_result[here_fast][here] < here_cost)
			continue;

		long long there_cost;
		int there;
		int there_fast;

		if (here_fast == 1)
			there_fast = 0;
		else
			there_fast = 1;

		for (int i = 0; i < adj[here].size(); i++)
		{
			//늑대가 빠르게 가는 경우
			if (here_fast == 1)
				there_cost = here_cost + (long long)(adj[here][i].first); //보통으로 가는 경우가 here_cost + (adj[here][i].first * 2) 이다

			//늑대가 느리게 가는 경우
			else
				there_cost = here_cost + (long long)(adj[here][i].first * 4);

			there = adj[here][i].second;

			if (there_cost < wolf_result[there_fast][there])
			{
				wolf_result[there_fast][there] = there_cost;
				pq.push(make_pair(make_pair(-there_cost, there), there_fast)); //((-비용,위치),빠르게 갈때인지 느리게 갈때인지(1:빠르게, 0:느리게))
			}

		}

	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b;
		long long d;

		cin >> a >> b >> d;

		adj[a].push_back(make_pair(d, b));
		adj[b].push_back(make_pair(d, a));
	}

	FoxSolve();
	WolfSolve();

	for (int i = 1; i <= n; i++)
	{
		if (fox_result[i] < min(wolf_result[0][i], wolf_result[1][i]))
			result++;
	}

	cout << result << "\n";

	return 0;
}