题目链接：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 airport more quickly than other transports. There are two types of trains in Airport-Express, the Economy-Xpressand 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 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.

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

题意：

在Iokh市中，机场快线是市民从市内去机场的首选交通工具。机场快线分为经济线和商业线两种，线路，速度和价钱都不同。你有一张商业线车票，可以做一站商业线，而其他时候只能乘坐经济线。假设换乘时间忽略不计，你的任务是找一条去机场最快的路线。

分析：

商业线只能坐一站，可枚举是哪一站，比较所有可能下的最优解。

假如我们用商业线车票从车站a坐到车站b，则从起点到a、从b到终点这两部分线路对于经济线网络来说应该都是最短路。换句话说，我们只需要从七点开始、到终点结束做两次最短路，记录下从起点到每个点a的最短时间f(a)，和从每个点b到终点的最短时间g(b)，总时间为f(a)+T(a， b)+g(b)，其中T(a, b)为商业线用时。求这个值得最小。

对于路径的输出，因为已记录在p中，因而可通过递归操作打印路径。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
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<Edge> edges;
vector<int> 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<HeapNode> 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;
}

UVA 11374 Airport Express 机场快线 Dijistra+路径