概要
有向グラフと目標頂点が与えられる.
目標頂点への往復経路が最も大きい頂点を探す.
解法
Dijkstraやるだけ.
復路の計算は与えられたグラフに対してDijkstra法を使えば簡単に求まる.
往路の計算は与えられたグラフの辺を逆向きにしたグラフにDijkstra法を使うと楽.
別の方法でもできる気はするが...
const int INF = 10000000; typedef int Weight; struct Edge{ int from, to; Weight weight; Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { } }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; bool operator<(const Edge &a, const Edge &b){ return a.weight > b.weight; } void dijkstra(const Graph &g, int s, vector<Weight> &dist, vector<int> &prev){ int n = g.size(); dist.assign(n, INF); dist[s] = 0; prev.assign(n, -1); priority_queue<Edge> Q; Q.push(Edge(-2, s, 0)); while(!Q.empty()){ Edge e = Q.top(); Q.pop(); if(prev[e.to] != -1) continue; prev[e.to] = e.from; EACH(i, g[e.to]){ if(dist[i->to] > dist[i->from] + i->weight){ dist[i->to] = dist[i->from] + i->weight; Q.push(Edge(i->from, i->to, dist[i->to])); } } } } int N, M, X; int main(){ scanf("%d%d%d", &N, &M, &X); Graph g(N+1), h(N+1); for(int i = 0; i < M; ++i){ int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a].push_back(Edge(a, b, c)); h[b].push_back(Edge(b, a, c)); } vector<Weight> dist1(N+1), dist2(N+1); vector<int> prev(N+1); dijkstra(g, X, dist1, prev); dijkstra(h, X, dist2, prev); int res = 0; for(int i = 1; i <= N; ++i) res = max(res, dist1[i] + dist2[i]); printf("%d\n", res); return 0; }