Week7：TT的旅行日记——最短路算法-阿南达文事网

Week7：TT的旅行日记——最短路算法

题目描述
众所周知，TT 有一只魔法猫。
今天他在 B 站上开启了一次旅行直播，记录他与魔法猫在喵星旅游时的奇遇。 TT 从家里出发，准备乘坐猫猫快线前往喵星机场。猫猫快线分为经济线和商业线两种，它们的速度与价钱都不同。当然啦，商业线要比经济线贵，TT 平常只能坐经济线，但是今天 TT 的魔法猫变出了一张商业线车票，可以坐一站商业线。假设 TT 换乘的时间忽略不计，请你帮 TT 找到一条去喵星机场最快的线路，不然就要误机了！

输入格式
输入包含多组数据。每组数据第一行为 3 个整数 N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100)，即猫猫快线中的车站总数，起点和终点（即喵星机场所在站）编号。

下一行包含一个整数 M (1 ≤ M ≤ 1000)，即经济线的路段条数。

接下来有 M 行，每行 3 个整数 X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐经济线在车站 X 和车站 Y 之间往返，其中单程需要 Z 分钟。

下一行为商业线的路段条数 K (1 ≤ K ≤ 1000)。

接下来 K 行是商业线路段的描述，格式同经济线。

所有路段都是双向的，但有可能必须使用商业车票才能到达机场。保证最优解唯一。

输出格式
对于每组数据，输出3行。第一行按访问顺序给出 TT 经过的各个车站（包括起点和终点），第二行是 TT 换乘商业线的车站编号（如果没有使用商业线车票，输出"Ticket Not Used"，不含引号），第三行是 TT 前往喵星机场花费的总时间。

注意：本题不忽略多余的空格和制表符，且每一组答案间要输出一个换行

输入样例

输出样例

1 2 4
2
5

题目分析
首先其实这个残念的输出格式导致的最大的问题其实不是WA而是PE，毕竟最短路就是个套模板的过程。

但是这道题并不是赤裸裸的最短路问题，它在此基础上增加了一个商业线，哦鬼鬼。

不过还好这个商业线只需要选择一条。

一个可行的思路是：

对于起点s，使用以所有经济线为边的图跑一遍到所有点的最短路，存储为dis1[i]。
对于终点e，也跑一遍最短路，存储为dis2[i]。
然后遍历所有的商业线(u,v,w)，康康dis1[u]+w+dis2[v]会不会比直接使用dis1[e]/dis2[s]更快，如果会的话就记下来。

这样下来最短的那条路就是我们记下来的所有的方式里耗时最短的那个了。

当然了这道题还要求记录路径，跑最短路时直接记下每个节点的父节点即可，就是输出的时候要注意遍历输出时先进先出还是先进后出之类的问题。

具体的可以参考代码：

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#include <stack>
const int inf = 0x3f3f3f3f;using namespace std;struct Edge
{int u, v, w;Edge(int _u, int _v, int _w){u = _u;v = _v;w = _w;}
};vector<Edge>economy[501];
vector<Edge>business;int dis1[501];
int dis2[501];
int vis[501];
int path1[501];//记录路径
int path2[501];void SPFA(int source, int* dis, int* path)
{for (int i = 0; i < 501; i++){*(path + i) = source;}queue<int>q;q.push(source);dis[source] = 0;vis[source] = 1;while (!q.empty()){int cur = q.front();q.pop();vis[cur] = 0;for (int i = 0; i < economy[cur].size(); i++){int v = economy[cur][i].v;int w = economy[cur][i].w;if (dis[v] > dis[cur] + w)//松弛{dis[v] = dis[cur] + w;path[v] = cur;if (!vis[v]){q.push(v);vis[v] = 1;}}}}
}void print(bool isbusiness, int su, int sv, int start, int end, int time)
{stack<int>s;if (isbusiness){int p = su;while (p != start){s.push(p);p = path1[p];}cout << start;while (!s.empty()){cout << " " << s.top();s.pop();}cout << " " << sv;p = sv;while (p != end){p = path2[p];cout << " " << p;}cout << endl << su << endl;cout << time << endl;}else{int p = end;while (p != start){s.push(p);p = path1[p];}cout << start;while (!s.empty()){cout << " " << s.top();s.pop();}cout << endl << "Ticket Not Used" << endl;cout << time << endl;}}int main()
{int EndlCounter = 0;bool isBusiness;int n, s, e;int m, k;while (cin >> n){if (!EndlCounter){EndlCounter = 1;}else{cout << endl;}cin >> s >> e;for (int i = 0; i < 501; i++) economy[i].clear();business.clear();cin >> m;//经济线的数目for (int i = 0, x, y, z; i < m; i++){cin >> x >> y >> z;economy[x].push_back(Edge(x, y, z));economy[y].push_back(Edge(y, x, z));}cin >> k;//商业线的数目for (int i = 0, x, y, z; i < k; i++){cin >> x >> y >> z;business.push_back(Edge(x, y, z));}memset(vis, 0, sizeof vis);memset(dis1, inf, sizeof dis1);SPFA(s, dis1, path1);memset(vis, 0, sizeof vis);memset(dis2, inf, sizeof dis2);SPFA(e, dis2, path2);int ans1 = inf;//走商业线的距离int stationu = 0;//走商业时的中转站int stationv = 0;for (int i = 0; i < business.size(); i++){int u = business[i].u;int v = business[i].v;int w = business[i].w;int tem1 = dis1[u] + dis2[v] + w;int tem2 = dis1[v] + dis2[u] + w;int temp,temu,temv;if (tem1 > tem2){temp = tem2;temu = v;temv = u;}else{temp = tem1;temu = u;temv = v;}if (ans1 > temp){stationu = temu;stationv = temv;ans1 = temp;}}int time = 0;if (ans1 > dis1[e]){isBusiness = false;time = dis1[e];}else{isBusiness = true;time = ans1;}print(isBusiness, stationu, stationv, s, e, time);}
}