Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem D: Airport Express

In a small city called Iokh, a train service, Airport-Express, takes residents to the airport more quickly than other transports. There are two types of trains in Airport-Express, the Economy-Xpress and the Commercial-Xpress. They travel at different speeds, take different routes and have different costs.

Jason is going to the airport to meet his friend. He wants to take the Commercial-Xpress which is supposed to be faster, but he doesn'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.

Input

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 M lines 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.

Output

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.

Sample Input

4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

Sample Output

1 2 4
2
5

---

Problemsetter: Raymond Chun
Originally appeared in CXPC, Feb. 2004

題目描述：

要求從起點到終點的最短路，但是 Jason 有一次機會使用特殊道路，
而這條特殊道路有可能使最短路更短，求最短的最短路徑。

並且輸出路徑走法。

題目解法：

無向圖正權最短路，代碼中使用 SPFA 計算。

分別對起點和終點各做一次 SPFA，然後對於特殊道路做窮舉，即可在 O(1) 時間內找到變更的最短路徑。

輸出稍微麻煩了些。

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge {
    int to, v;
    edge(int a, int b):
        to(a), v(b) {}
};
vector<edge> g[505];
void spfa(int n, int st, int dist[], int prev[]) {
    int i, j, k;
    int tn, inq[505] = {};
    queue<int> Q;
    for(i = 1; i <= n; i++)
        dist[i] = 0xfffffff;
    dist[st] = 0, Q.push(st);
    while(!Q.empty()) {
        tn = Q.front(), Q.pop();
        inq[tn] = 0;
        for(i = 0; i < g[tn].size(); i++) {
            if(dist[g[tn][i].to] > dist[tn] + g[tn][i].v) {
                dist[g[tn][i].to] = dist[tn] + g[tn][i].v;
                prev[g[tn][i].to] = tn;
                if(inq[g[tn][i].to] == 0) {
                    inq[g[tn][i].to] = 1;
                    Q.push(g[tn][i].to);
                }
            }
        }
    }
}
int main() {
    int n, m, st, ed;
    int i, j, k, x, y, v;
    int cases = 0;
    while(scanf("%d %d %d", &n, &st, &ed) == 3) {
        if(cases++)    puts("");
        for(i = 1; i <= n; i++)
            g[i].clear();
        scanf("%d", &m);
        while(m--) {
            scanf("%d %d %d", &x, &y, &v);
            g[x].push_back(edge(y, v));
            g[y].push_back(edge(x, v));
        }
        int distST[505], distED[505];
        int prevST[505], prevED[505];
        spfa(n, st, distST, prevST);
        spfa(n, ed, distED, prevED);
        int rx = -1, ry = -1, mn = distST[ed];
        scanf("%d", &m);
        while(m--) {
            scanf("%d %d %d", &x, &y, &v);
            if(distST[x] + distED[y] + v < mn)  {
                mn = distST[x] + distED[y] + v;
                rx = x, ry = y;
            }
            if(distST[y] + distED[x] + v < mn)  {
                mn = distST[y] + distED[x] + v;
                rx = y, ry = x;
            }   
        }
        int rrx = rx;
        if(rx == -1)  {
            while(st != ed) {
                printf("%d ", st);
                st = prevED[st];
            }
            printf("%d\n", ed);
        } else {
            int buffer[505], bidx = 0;
            while(rx != st) {
                buffer[bidx++] = rx;
                rx = prevST[rx];
            }
            buffer[bidx++] = st;
            for(i = bidx-1; i >= 0; i--) {
                printf("%d", buffer[i]);
                if(i)    putchar(' ');
            }
            while(ry != ed) {
                printf(" %d", ry);
                ry = prevED[ry];
            }
            printf(" %d\n", ed);
        }
        if(rrx == -1)
            puts("Ticket Not Used");
        else
            printf("%d\n", rrx);
        printf("%d\n", mn);
    }
    return 0;
}