문제

문제 링크 : https://www.acmicpc.net/problem/1238

풀이

이 문제에서는 각 간선은 방향이 있기 때문에 각 정점에서 x까지 오는 길과 x에서 각 정점으로 가는 길이 다를 수 있다.

그래서 처음엔 다익스트라 함수에 x를 시작점으로 넣고 x에서 각 정점까지의 최단 거리를 구하고, 각 정점을 for 문으로 돌면서 매 번 다익스트라 함수에 해당 정점을 시작점으로 넣고 x까지의 최단 거리를 구했다.

하지만 정점이 최대 1000개까지 주어질 수 있기 때문에 최악의 경우엔 다익스트라 함수를 1001번 사용하게 되기 때문에 비효율적이다.

그래프를 입력 받을 때 역방향 그래프도 입력을 받으면 각 정점에서 x까지의 최단 거리도 다익스트라 함수를 단 한 번 돌려서 알 수 있다.

역방향 그래프에서 시작점을 x로 잡고 다익스트라 알고리즘을 사용하면 정방향 그래프에서 각 정점에서 x까지의 최단 거리를 구하는 것과 동일하기 때문이다.

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9 + 7;
int dist_x_to_n[1001];
vector<int> dist[2];
vector<pair<int, int>> graph[2][1001];
int n, m, x;


void dijkstra(int k) {
	dist[k][x] = 0;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push({0,x});

	while (!q.empty()) {
		int d = q.top().first;
		int now = q.top().second;
		q.pop();

		if (d > dist[k][now]) continue;

		for (int i = 0; i < graph[k][now].size(); i++) {
			int next = graph[k][now][i].second;
			int next_d = d + graph[k][now][i].first;

			if (next_d < dist[k][next]) {
				dist[k][next] = next_d;
				q.push({ next_d,next });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	fill_n(dist_x_to_n, 1001, INF);

	cin >> n >> m >> x;

	for (int i = 0; i < m; i++) {
		int a, b, t;
		cin >> a >> b >> t;
		graph[0][a].push_back({t,b});
		graph[1][b].push_back({ t,a });
	}

	dist[0].resize(n + 1, INF);
	dist[1].resize(n + 1, INF);

	dijkstra(0);
	dijkstra(1);

	int result = 0;

	for (int i = 1; i <= n; i++) {
		result = max(result, dist[0][i] + dist[1][i]);
	}

	cout << result << '\n';

	return 0;
}