首页 > 代码库 > uva 11374

uva 11374

2024-07-02 01:37:30   240人阅读

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 Zminutes 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

最短路
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 
  7 using namespace std;
  8 
  9 const int MAX_N = 505;
 10 const int edge = 2005;
 11 const int INF = (1 << 29);
 12 struct node {
 13         int d,u;
 14         bool operator < (const node &rhs) const {
 15                 return d > rhs.d;
 16         }
 17 };
 18 
 19 int N,S,E,M,K;
 20 int first[MAX_N],v[edge],Next[edge];
 21 int w[edge],d1[MAX_N],d2[MAX_N];
 22 int x[MAX_N * 2],y[MAX_N * 2],w1[MAX_N * 2];
 23 bool done[MAX_N];
 24 int p1[MAX_N],p2[MAX_N];
 25 int ou[MAX_N],tem[MAX_N];
 26 
 27 void add_edge(int id,int u) {
 28         int e = first[u];
 29         Next[id] = e;
 30         first[u] = id;
 31 }
 32 
 33 void dijkstra(int s,int *d,int *p) {
 34         fill(p + 1,p + N + 1,-1);
 35         for(int i = 1; i <= N; ++i) d[i] = INF;
 36         d[s] = 0;
 37         memset(done,0,sizeof(done));
 38         priority_queue<node > q;
 39         q.push(node {d[s],s});
 40 
 41         while(!q.empty()) {
 42                 node x = q.top(); q.pop();
 43                 int u = x.u;
 44                 if(done[u]) continue;
 45                 done[u] = 1;
 46                 for(int e = first[u]; e != -1; e = Next[e]) {
 47                         if(d[ v[e] ] > d[u] + w[e]) {
 48                                 d[ v[e] ] = d[u] + w[e];
 49                                 q.push(node { d[ v[e] ],v[e]});
 50                                 p[ v[e] ] = u;
 51 
 52                         }
 53                 }
 54 
 55         }
 56 }
 57 
 58 void output(int id) {
 59         int len = 0;
 60         int len1 = 0;
 61 
 62         if(id != 0) {
 63                 int a,b;
 64                 a = id < 0 ? y[-id] :x[id];
 65                 b = id < 0 ? x[-id] :y[id];
 66                 for(int p = a; p != -1; p = p1[p]) {
 67                         tem[len++] =  p;
 68                 }
 69                 for(int i = len - 1; i >= 0 ; --i) {
 70                         ou[len1++] = tem[i];
 71                 }
 72                 //printf("b= %d\n",p2[b]);
 73                 for(int p = b; p != -1; p = p2[p]) {
 74                         ou[len1++] = p;
 75                 }
 76         } else {
 77 
 78                 for(int p = E; p != -1; p = p1[p]) {
 79                         ou[len1++] = p;
 80                 }
 81                 for(int i = 0,j = len1 - 1; i < j; ++i,--j) {
 82                         swap(ou[i],ou[j]);
 83                 }
 84         }
 85 
 86         for(int i = 0; i < len1; ++i) {
 87                 printf("%d%c",ou[i],i == len1 - 1 ? ‘\n‘ : ‘ ‘);
 88         }
 89 }
 90 
 91 void solve() {
 92         dijkstra(S,d1,p1);
 93         dijkstra(E,d2,p2);
 94         int ans = d1[E],id = 0;
 95         //printf("ans = %d\n",ans);
 96         for(int i = 1; i <= K; ++i) {
 97                 if(ans > d1[ x[i]] + d2[ y[i] ] + w1[i]) {
 98                         ans = d1[ x[i] ] + d2[ y[i] ] + w1[i];
 99                         id = i;
100                 }
101                 if(ans > d1[ y[i] ] + d2[ x[i] ] + w1[i]) {
102                         ans = d1[ y[i] ] + d2[ x[i] ] + w1[i];
103                         id = -i;
104                 }
105         }
106 
107         output(id);
108         if(id == 0) {
109                 printf("Ticket Not Used\n");
110         } else {
111                 printf("%d\n",id < 0 ? y[-id] : x[id]);
112         }
113 
114         printf("%d\n",ans);
115 
116 
117 }
118 
119 int main()
120 {
121     //freopen("sw.in","r",stdin);
122     bool ok = 0;
123     while(~scanf("%d%d%d",&N,&S,&E)) {
124            if(ok) printf("\n");
125            ok = 1;
126            scanf("%d",&M);
127            for(int i = 1; i <= N; ++i) first[i] = -1;
128            for(int i = 0; i < 2 * M; i += 2) {
129                 int u;
130                 scanf("%d%d%d",&u,&v[i],&w[i]);
131                 v[i + 1] = u;
132                 w[i + 1] = w[i];
133                 add_edge(i,u);
134                 add_edge(i + 1,v[i]);
135            }
136 
137            scanf("%d",&K);
138            for(int i = 1; i <= K; ++i) {
139                 scanf("%d%d%d",&x[i],&y[i],&w1[i]);
140            }
141 
142            solve();
143 
144 
145     }
146 
147     //cout << "Hello world!" << endl;
148     return 0;
149 }
View Code

 


联系
我们