題目鏈接：UVA 11374 Airport Express
[Submit] [Go Back] [Status]
Description
Problem D: Airport Express
In a small city called Iokh, a train service, Airport-Express, takes residents to the airpZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcnQgbW9yZSBxdWlja2x5IHRoYW4gb3RoZXIgdHJhbnNwb3J0cy4gVGhlcmUgYXJlIHR3byB0eXBlcyBvZiB0cmFpbnMgaW4gQWlycG9ydC1FeHByZXNzLCB0aGUgPHN0cm9uZz5FY29ub215LVhwcmVzczwvc3Ryb25nPmFuZCB0aGUgPHN0cm9uZz5Db21tZXJjaWFsLVhwcmVzczwvc3Ryb25nPi4KIFRoZXkgdHJhdmVsIGF0IGRpZmZlcmVudCBzcGVlZHMsIHRha2UgZGlmZmVyZW50IHJvdXRlcyBhbmQgaGF2ZSBkaWZmZXJlbnQgY29zdHMuPC9wPgo8cD4KSmFzb24gaXMgZ29pbmcgdG8gdGhlIGFpcnBvcnQgdG8gbWVldCBoaXMgZnJpZW5kLiBIZSB3YW50cyB0byB0YWtlIHRoZSBDb21tZXJjaWFsLVhwcmVzcyB3aGljaCBpcyBzdXBwb3NlZCB0byBiZSBmYXN0ZXIsIGJ1dCBoZSBkb2Vzbg=="t have enough money. Luckily he has a ticket for the Commercial-Xpress which can take him one station forward. If he used the ticket wisely, he might end up saving a lot of time. However, choosing the best time to use the ticket is not easy for him.
Jason now seeks your help. The routes of the two types of trains are given. Please write a program to find the best route to the destination. The program should also tell when the ticket should be used.
The input consists of several test cases. Consecutive cases are separated by a blank line.
The first line of each case contains 3 integers, namely N, S and E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ N), which represent the number of stations, the starting point and where the airport is located respectively.
There is an integer M (1 ≤ M ≤ 1000) representing the number of connections between the stations of the Economy-Xpress. The next Mlines give the information of the routes of the Economy-Xpress. Each consists of three integers X, Y and Z (X, Y ≤ N, 1 ≤ Z ≤ 100). This means X and Y are connected and it takes Z minutes to travel between these two stations.
The next line is another integer K (1 ≤ K ≤ 1000) representing the number of connections between the stations of the Commercial-Xpress. The next K lines contain the information of the Commercial-Xpress in the same format as that of the Economy-Xpress.
All connections are bi-directional. You may assume that there is exactly one optimal route to the airport. There might be cases where you MUST use your ticket in order to reach the airport.
For each case, you should first list the number of stations which Jason would visit in order. On the next line, output "Ticket Not Used" if you decided NOT to use the ticket; otherwise, state the station where Jason should get on the train of Commercial-Xpress. Finally, print the total time for the journey on the last line. Consecutive sets of output must be separated by a blank line.
4 1 4 4 1 2 2 1 3 3 2 4 4 3 4 5 1 2 4 3
1 2 4 2 5
題意：
在Iokh市中，機場快線是市民從市內去機場的首選交通工具。機場快線分為經濟線和商業線兩種，線路，速度和價錢都不同。你有一張商業線車票，可以做一站商業線，而其他時候只能乘坐經濟線。假設換乘時間忽略不計，你的任務是找一條去機場最快的路線。
分析：
商業線只能坐一站，可枚舉是哪一站，比較所有可能下的最優解。
假如我們用商業線車票從車站a坐到車站b，則從起點到a、從b到終點這兩部分線路對於經濟線網絡來說應該都是最短路。換句話說，我們只需要從七點開始、到終點結束做兩次最短路，記錄下從起點到每個點a的最短時間f(a)，和從每個點b到終點的最短時間g(b)，總時間為f(a)+T(a， b)+g(b)，其中T(a, b)為商業線用時。求這個值得最小。
對於路徑的輸出，因為已記錄在p中，因而可通過遞歸操作打印路徑。
代碼：
#include#include #include #include #include using namespace std; #define maxn 550 #define INF 0x3f3f3f3f struct Edge { int from, to, dist; }; struct HeapNode { int d, u; bool operator < (const HeapNode& rhs) const { return d > rhs.d; } }; int n, S, E; vector edges; vector G[maxn]; bool vis[maxn]; int d[maxn], p[maxn], p1[maxn], p2[maxn]; void Init(int n) { for(int i = 0; i <= n; i++) G[i].clear(); edges.clear(); } void addEdge(int from, int to, int dist) { // 無向圖，每條邊需要調用兩次addEdge edges.push_back((Edge){from, to, dist}); int x = edges.size(); G[from].push_back(x-1); } void Dijkstra(int s) { priority_queue q; for(int i = 1; i <= n; i++) d[i] = INF; d[s] = 0; memset(vis, false, sizeof(vis)); q.push((HeapNode){0, s}); while(!q.empty()) { HeapNode x = q.top(); q.pop(); int u = x.u; if(vis[u]) continue; vis[u] = true; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u]+e.dist) { d[e.to] = d[u]+e.dist; p[e.to] = G[u][i]; q.push((HeapNode){d[e.to], e.to}); } } } } void printA(int k) { if(k == S) { printf("%d", k); return ; } int t = p1[k]; Edge& e = edges[t]; printA(e.from); printf(" %d", k); } void printB(int k) { if(k == E) { printf(" %d", k); return; } printf(" %d", k); int t = p2[k]; Edge& e = edges[t]; printB(e.from); } int main() { int count = 0; int N, M, K, X, Y, Z, f[maxn], g[maxn]; while(~scanf("%d%d%d", &N, &S, &E)) { if(count++) printf("\n"); n = N; scanf("%d", &M); Init(N); while(M--) { scanf("%d%d%d", &X, &Y, &Z); addEdge(X, Y, Z); addEdge(Y, X, Z); } Dijkstra(S); memcpy(f, d, sizeof(d)); memcpy(p1, p, sizeof(p)); Dijkstra(E); memcpy(g, d, sizeof(d)); memcpy(p2, p, sizeof(p)); scanf("%d", &K); int ans = f[E]; int st = -1, ed = -1; while(K--) { scanf("%d%d%d", &X, &Y, &Z); if(ans > Z+f[X]+g[Y]) { ans = Z+f[X]+g[Y]; st = X; ed = Y; } if(ans > Z+f[Y]+g[X]) { ans = Z+f[Y]+g[X]; st = Y; ed = X; } } if(st == -1) { printA(E); printf("\nTicket Not Used\n"); } else { printA(st); printB(ed); printf("\n%d\n", st); } printf("%d\n", ans); } return 0; }
