3268:Silver Cow Party

PKU 蟻本

keyword

Dijkstra　C++

概要

有向グラフが与えられる。ある目的地に行って戻ってくる(最短経路を使って)までの合計時間が最大になるものをみつけ、その合計時間を求める問題。ノード数は1000以下。
ダイクストラするだけ。帰りは辺を逆に張ればよい。

int dist[1001][1001];
int back[1001];
int go[1001];

typedef pair< int,int>  edge;

int main(){
    int i, j;
    int n, x, t, m, from, to;
    n = readint();
    m = readint();
    x = readint()-1;
    REP(i,n)REP(j,n) dist[i][j] = 1<<29;
    REP(i,m){
        from = readint()-1;
        to = readint()-1;
        t = readint();
        dist[from][to] = min(t, dist[from][to]);
    }
    REP(i,n) go[i] = 1<<29;
    REP(i,n) back[i] = 1<<29;

    {
        priority_queue<edge,vector<edge>,greater<edge> > Q;
        REP(i,n)if(dist[x][i] < 1<<29) Q.push( MP(dist[x][i],i) );
        back[x] = 0;
        while(!Q.empty()){
            edge tp = Q.top(); Q.pop();
            if(back[tp.second] < 1<<29) continue;
            back[tp.second] = tp.first;
            REP(i,n)if(back[i]==1<<29 && dist[tp.second][i] < 1<<29){
                Q.push( MP(tp.first + dist[tp.second][i], i) );
            }
        }
    }

    {
        priority_queue<edge,vector<edge>,greater<edge> > Q;
        REP(i,n)if(dist[i][x] < 1<<29) Q.push( MP(dist[i][x],i) );
        go[x] = 0;
        while(!Q.empty()){
            edge tp = Q.top(); Q.pop();
            if(go[tp.second] < 1<<29) continue;
            go[tp.second] = tp.first;
            REP(i,n)if(go[i]==1<<29 && dist[i][tp.second] < 1<<29){
                Q.push( MP(tp.first + dist[i][tp.second], i) );
            }
        }
    }

    int ans = 0;
    REP(i,n) ans = max(ans, go[i] + back[i]);

    printf("%d\n",ans);
    return 0;
}