문제 출처

1. 문제설명

  • N개의 정점과 M개의 간선으로 이뤄진 그래프가 있다.

  • 목적지 x가 주어질 때, 정점 간 이동비용이 가장 큰 비용을 구하라

  • 문제 분류
    • Graph, Dijkstra


2. 알고리즘 설계

  • 다익스트라 알고리즘 문제이다.
    • 음의 가중치가 없을 때 최단거리 찾기 알고리즘
  • 모든 정점 i에 대해 Dijkstra(i, dest)를 해주면 되는데 문제를 보면 오고 가는 경로라고 되어있다.
  • 즉, Dijkstra(i, dest) + Dijkstra(dest, i)에 대한 최대값을 구해주는 문제이다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

const int SZ = 1002, INF = 0x3f3f3f3f;
int n, m, dest, ans;
vector<pii> adj[SZ];
bool vis[SZ];


int solve(int src, int dst) {
	int D[SZ];
	fill(D+1, D+n+1, INF);

	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, src});
	D[src] = 0;

	for(int u, v, w, dw; !pq.empty();) {
		tie(w, u) = pq.top();
		pq.pop();

		for(auto nxt : adj[u]) {
			tie(dw, v) = nxt;

			if(dw + w < D[v]) {
				D[v] = dw + w;
				pq.push({dw+w, v});
			}
		}
	}

	return D[dst];
}

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

	cin >> n >> m >> dest;
	for(int u, v, c; m--;) {
		cin >> u >> v >> c;
		adj[u].push_back({c, v});
	}

	int ans = 0;
	for(int i=1; i<=n; i++)
		ans = max(ans, solve(i, dest) + solve(dest, i));
	cout << ans;

	return 0;
}