0w1

UVA 11374 Airport Express ( Dijkstra + Route printing )

UVa Online Judge
從起點和從終點各做一次單源最短路徑,並紀錄pre 陣列方便打印最短路徑。因為經濟線只能用一次,所以枚舉所有可以用的經濟線,還有一次完全不用經濟線的情況,比較哪個最好。時間複雜度 O( M lg N + K )

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 500 + 5;
const int MAXM = 1e3 + 3;
const int INF = 1e9;

int n, s, e;
int m;
vector<pii> es[MAXN]; // cost, destination
int k;
int expx[MAXM], expy[MAXM], expz[MAXM];

int vis[MAXN];
void dijkstra(int s, int *d, int *pre){
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push( pii( 0, s ) );
    fill( d, d + MAXN, INF );
    d[s] = 0;
    memset( vis, 0, sizeof(vis) );
    fill( pre, pre + MAXN, -1 );
    while( !pq.empty() ){
        int c = pq.top().first, u = pq.top().second;
        pq.pop();
        if( vis[ u ] ) continue;
        vis[ u ] = 1;
        for(pii p: es[u]){
            int nc = p.first, nu = p.second;
            if( d[ nu ] > d[ u ] + nc ){
                d[ nu ] = d[ u ] + nc;
                pre[ nu ] = u;
                pq.push( pii( d[ nu ], nu ) );
            }
        }
    }
}

int d_s[MAXN], d_e[MAXN];
int p_s[MAXN], p_e[MAXN];
void solve(){
    dijkstra( s, d_s, p_s );
    dijkstra( e, d_e, p_e );
    int ans1 = d_s[ e ], ans2 = e, ans3 = -1;
    for(int i = 0; i < k; ++i){ // enumerate possible express lines
        int costa = d_s[ expx[i] ] + expz[i] + d_e[ expy[i] ]; // bidirectional, so check *2
        int costb = d_s[ expy[i] ] + expz[i] + d_e[ expx[i] ];
        if( ans1 > costa ) ans1 = costa, ans2 = expx[i], ans3 = expy[i];
        if( ans1 > costb ) ans1 = costb, ans2 = expy[i], ans3 = expx[i];
    }
    stack<int> stk1; int tmp = ans2;
    while( tmp != -1 ){
        stk1.push( tmp );
        tmp = p_s[ tmp ];
    }
    if( ans3 == -1 ){ // did not use ticket
        for( ; !stk1.empty(); stk1.pop() )
            printf("%d%c", stk1.top(), stk1.size() == 1 ? '\n' : ' ');
        puts("Ticket Not Used");
        printf("%d\n", ans1);
        return;
    }
    queue<int> que2; tmp = ans3;
    while( tmp != -1 ){
        que2.push( tmp );
        tmp = p_e[ tmp ];
    }
    for( ; !stk1.empty(); stk1.pop() )
        printf("%d ", stk1.top());
    for( ; !que2.empty(); que2.pop() )
        printf("%d%c", que2.front(), que2.size() == 1 ? '\n' : ' ');
    printf("%d\n%d\n", ans2, ans1);
}

void init(){
    for(int i = 1; i <= n; ++i)
        es[i].clear();
}

int main(){
    bool first = true;
    while( scanf("%d%d%d", &n, &s, &e) == 3 ){
        if( first ) first = false;
        else puts("");
        init();
        scanf("%d", &m);
        for(int i = 0; i < m; ++i){
            int x, y, z; scanf("%d%d%d", &x, &y, &z);
            es[x].push_back( pii( z, y ) );
            es[y].push_back( pii( z, x ) );
        }
        scanf("%d", &k);
        for(int i = 0; i < k; ++i)
            scanf("%d%d%d", &expx[i], &expy[i], &expz[i]);
        solve();
    }
    return 0;
}