C++ / 1238 / 파티 ( 다익스트라 )

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

문제 요약

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있습니다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비합니다.

 

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 합니다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원합니다.

 

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구해야합니다.

문제 풀이

이 문제는 가는거리와 오는거리가 필요합니다. 그래서 그래프도 2개를 만들고 dist 배열도 2개를 만들어야합니다.

1. 그래프 입력을 받습니다. 하나는 가는 길 그래프 ( 정방향 ), 나머지 하나는 오는 길 그래프 ( 역방향 )으로 받습니다.

2. 데이크스트라 함수도 2개 만드는데 ( 한개로 만들어도 됩니다. 그냥 귀찮아서 두개로 쪼갬 ) 각각 x로 부터 탐색을 해줍니다.

x로 부터 탐색을 하는 이유는 x로 부터 마을까지의 최단 거리를 정방향과 역방향 그래프로 탐색하게 되면 각각 오는 거리 가는 거리를 저장할 수 있습니다.3. 각 마을에 저장된 오는거리 가는거리의 합 중에 최댓값을 뽑습니다.

주의할 점

양방향 그래프로 만들면 된다고 생각 하기 쉽습니다.

문제에 단방향이라고 명시 되어있고 양방향으로 만들면 없는 길을 만들게 되어 잘못된 최단거리를 계산하게 됩니다.

코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

// 파티 갈때와 올때 2개씩
int dist[1004];
int dist2[1004];
vector<pair<int, int>>v[10004];
vector<pair<int, int>>v2[10004];
int n, m, x;
int ans = 0;


void dijkstra(int start)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push({ 0,start });
	dist[start] = 0;

	while (!pq.empty())
	{
		int cost = pq.top().first;
		int now = pq.top().second;
		pq.pop();

		if (dist[now] < cost)
		{
			continue;
		}
		for (auto i : v[now])
		{
			int nextNode = i.first;
			int nextCost = i.second + cost;

			if (dist[nextNode] > nextCost)
			{
				dist[nextNode] = nextCost;
				pq.push({ nextCost,nextNode });
			}
		}
	}
}
void dijkstra2(int start)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push({ 0,start });
	dist2[start] = 0;

	while (!pq.empty())
	{
		int cost = pq.top().first;
		int now = pq.top().second;
		pq.pop();

		if (dist2[now] < cost)
		{
			continue;
		}
		for (auto i : v2[now])
		{
			int nextNode = i.first;
			int nextCost = i.second + cost;

			if (dist2[nextNode] > nextCost)
			{
				dist2[nextNode] = nextCost;
				pq.push({ nextCost,nextNode });
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m >> x;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		// 가는길 벡터
		v[a].push_back({ b, c });
		// 오는길 벡터
		v2[b].push_back({ a, c });
	}
	fill(dist, dist + n + 1, 1e9);
	fill(dist2, dist2 + n + 1, 1e9);
	// 각 마을로 부터 x까지의 최단 거리 계산
	dijkstra(x);

	// x부터 각 마을까지 계산
	dijkstra2(x);


	// 오고 가는 거리 합
	for (int i = 1; i <= n; i++)
	{
		ans = max(ans, dist[i] + dist2[i]);
	}
	cout << ans;

	return 0;
}

예제

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

결과