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 CommercialXpress 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.
链接
https://cn.vjudge.net/problem/UVA-11374
题意
n个车站，m条经济线，k条商业线，线路是双向的，每条线路花费时间不同，现在你有一张商业线机票，可以坐一站商业线，而其他时候只能乘坐经济线，假设换乘时间不计，任务是找一条去机场最快的路线（从s到t）。注意有可能必须乘坐商业线才能到达目的地，保证最优解唯一。输出线路、乘坐商业线的站点号和最短时间。
题解
因为商业线只能坐一站，所以可以枚举坐的是哪一站，比较所有可能性下的最优解。如果可以在$O(1)$时间内解决计算出每种方案对应的最优方案，整个问题就可以在$O(K)$时间内解决，假设我们用商业线车票从车站a坐到车站b，则从起点到a、从a到终点这两部分线路对于“经济线网络”来说都应该是最短路。换句话说，我们只要从起点开始、到终点结束做两次单源最短路，记录下从起点到每个点x的最短时间f(x)和从每个点x到终点的最短时间g(x)，则总时间为f(a)+T(a, b)+f(b)，其中T(a,b)为从a坐一站商业线到b的时间。
算上预处理时间$O(mlogn)$，本算法的时间复杂度$O(mlongn + k)$。
——小白书P329
特别注意一下处理输出的路径，以及两个输出之间有一个空行。因为点数只有500，所以我用的是邻接矩阵版的dijkstra。
代码
| Status | Accepted |
|---|---|
| Length | 3132 |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 510;
int n, m;
int dist1[maxn], dist2[maxn], pre1[maxn], pre2[maxn];
bool vis[maxn];
int G[maxn][maxn];
vector <int> V1, V2;
void dijkstra(int s, int dist[], int pre[]) // 最短路
{
for (int i = 1; i <= n; ++i)
{
dist[i] = inf;
vis[i] = false;
pre[i] = -1;
}
dist[s] = 0;
pre[s] = -1;
for (int i = 1; i <= n; ++i)
{
int k = -1;
int Min = inf;
for (int j = 1; j <= n; ++j)
{
if (!vis[j] && dist[j] < Min)
{
Min = dist[j];
k = j;
}
}
if (k == -1)
break;
vis[k] = true;
for (int j = 1; j <= n; ++j)
{
if (!vis[j] && dist[k] + G[k][j] < dist[j])
{
dist[j] = dist[k] + G[k][j];
pre[j] = k;
}
}
}
}
int main()
{
// freopen("/Users/taifu/Codes/NOW/data.in", "r", stdin);
// freopen("/Users/taifu/Codes/NOW/data.out","w",stdout);
int s, t, k, u, v, w, a, b, kase = 0;
while (scanf("%d%d%d", &n, &s, &t) != EOF)
{
++kase;
scanf("%d", &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
G[i][j] = (i == j ? 0 : inf);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
G[u][v] = G[v][u] = w;
}
dijkstra(s, dist1, pre1); // 正向最短路
dijkstra(t, dist2, pre2); // 反向最短路
scanf("%d", &k);
int pos = -1, dis = dist1[t], tmp;
for (int i = 0; i < k; ++i)
{
scanf("%d%d%d", &u, &v, &w);
tmp = dist1[u] + w + dist2[v];
if (tmp < dis) // 坐商业线更快 u->v
{
dis = dist1[u] + w + dist2[v];
pos = u;
a = u, b = v;
}
tmp = dist1[v] + w + dist2[u];
if (tmp < dis) // 坐商业线更快 v->u
{
dis = dist1[v] + w + dist2[u];
pos = v;
a = v, b = u;
}
}
V1.clear(), V2.clear();
if (kase > 1) // 两个输出之间有一个空行
printf("\n");
if (pos == -1) // 不需要乘坐商业线
{
for (int i = t; i != -1; i = pre1[i])
V1.push_back(i);
printf("%d", V1[V1.size() - 1]);
for (int i = V1.size() - 2; i >= 0; --i) // 直接输出正向路径
printf(" %d", V1[i]);
printf("\n");
printf("Ticket Not Used\n");
}
else // 乘坐商业线
{
for (int i = a; i != -1; i = pre1[i])
V1.push_back(i);
for (int i = b; i != -1; i = pre2[i])
V2.push_back(i);
printf("%d", V1[V1.size() - 1]);
for (int i = V1.size() - 2; i >= 0; --i) // 路径1->a->b->路径2
printf(" %d", V1[i]);
for (int i = 0; i < V2.size(); ++i)
printf(" %d", V2[i]);
printf("\n");
printf("%d\n", pos);
}
printf("%d\n", dis);
}
}The end.
2018-08-20 星期一