POJ 3268: Silver Cow Party

概要

有向グラフと目標頂点が与えられる.
目標頂点への往復経路が最も大きい頂点を探す.

解法

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;
}