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