7-8 过年了，回家吧 （30 分）map dijkstra
小CC的家离学校有1000多公里，坐火车要数十个小时。每年春运之时，小CC总要绞尽脑汁寻找最合适的换乘路线。
小CC的换乘问题抽象如下：
地图上有N个城市，M条交通路线将城市两两相连。小CC需要经过若干条交通路线，从城市S回到城市T。途径每条交通路线都会消耗一定时间，在中转城市换乘也需要消耗一定时间，起点和终点的换乘时间不计算在内。现在请你编写程序，帮小CC规划回家的路，这条路必须是耗时最短的路径，如果有耗时相同的多条路径，选择其中换乘最少的一条。
例如，小CC要从厦门回到大同，下图是小CC回家时的线路图，图中的方块表示换乘时间，线路上的数字表示线路的旅途时间。
（本图仅作示意，不代表真实旅行时间和实际地理位置）
从图中可以看出，有多条路径可以选择，但是耗时最短的路径（耗时375）只有两条：
厦门->北京->大同，路途时间227+70，换乘时间78；
厦门->南昌->郑州->大同，旅途时间65+64+125，换乘时间40+81。
此时，小CC会选择换乘次数较少的第1条线路。
输入格式:
第一行为1个正整数N≤500，表示城市个数。
然后是N行，每行依次是城市名称和换乘时间。城市名称不超过40个字符，由大小写字母组成，换乘时间是不大于104的正整数。
接下来是一个正整数M≤3N，表示交通路线条数。
接着M行，每行三个元素，依次是两个城市名称和路线耗时（不大于104的正整数）。
最后一行依次给出起点S和目的地T的城市名称。
输出格式:
如果存在一条从起点到终点耗时最短的路线：
第一行输出耗时（起点终点的中转时间不计算在内）。
第二行按照从起点到终点的顺序输出沿途城市（包括起点终点），用->链接。
如果有多条耗时最短的路线，输出中转次数最少的一条。
如果不存在一条从起点到终点的路线：
输出一行：“Why not go home by plane?"
输入样例1:
示意图中的例子。
10
Datong 52
Xuzhou 87
Hefei 71
Nanchang 40
Zhengzhou 81
Shijiazhuang 56
Taiyuan 45
Nanjing 43
Beijing 78
Xiamen 55
22
Xiamen Beijing 227
Beijing Nanjing 170
Xiamen Hefei 95
Zhengzhou Shijiazhuang 41
Beijing Datong 70
Beijing Taiyuan 34
Taiyuan Datong 65
Taiyuan Shijiazhuang 19
Nanjing Hefei 10
Xuzhou Nanchang 102
Beijing Shijiazhuang 25
Xuzhou Beijing 157
Zhengzhou Xuzhou 37
Xiamen Xuzhou 139
Beijing Nanchang 201
Nanchang Xiamen 65
Zhengzhou Nanchang 64
Datong Zhengzhou 125
Hefei Xuzhou 46
Shijiazhuang Nanjing 198
Taiyuan Zhengzhou 43
Hefei Beijing 165
Xiamen Datong
输出样例1:
375
Xiamen->Beijing->Datong
输入样例2:
非连通图。仅有两条边，乌鲁木齐（新疆）-阿拉山口（新疆），乌兰察布（原称集宁，内蒙古）-呼和浩特（内蒙古）。不存在阿拉山口-乌兰察布路径。
4
Alashankou 50
Urumchi 65
Hohhot 69
Ulanqab 75
2
Urumchi Alashankou 96
Hohhot Ulanqab 125
Alashankou Ulanqab
输出样例2:
Why not go home by plane?
https://pintia.cn/problem-sets/1102099479966621696/problems/1102099508777295873
裸的DIJKSTRA 注意点是 1 字符串输入倒腾起来有点麻烦 用快乐map 2 要打印最短路径 3 要求换成次数最少
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
using namespace std;
const int MAXN = 505;
const int INF = 200000000;
int arr[MAXN][MAXN];
map <string, int> mp;
string srr[MAXN];
int dis[MAXN], ah[MAXN], pre[MAXN];
int N, M;
struct Node {
int pos, t, ht, from;
Node (int a, int b, int c, int d) {
pos = a; t = b; ht = c; from = d;
}
};
struct cmp {
bool operator() (Node &a, Node &b) {
if (a.t != b.t) return a.t < b.t;
return a.ht < b.ht;
}
};
void dijkstra(int s, int des) {
dis[s] = 0;
pre[s] = s;
priority_queue<Node, vector<Node>, cmp> pq;
pq.push(Node(s, 0, 0, s));
while (!pq.empty()) {
int p = pq.top().pos;
int t = pq.top().t;
int ht = pq.top().ht;
int f = pq.top().from;;
pq.pop();
if (dis[p] < t) continue;//时间最少
if (dis[p] == t && ah[p] <= ht) continue;//换乘次数最少
pre[p] = f;
dis[p] = t;
ah[p] = ht;
for (int i = 0; i < N; i++) {//接下来去i号都市
if (arr[p][i] != INF && i != p) {
int nt = arr[p][i] + t + arr[i][i];
if (i == des) nt -= arr[i][i];
if (nt > dis[i]) continue;
pq.push(Node(i, nt, ht + 1, p));
}
}
}
}
int main() {
scanf("%d", &N);
fill(dis, dis + MAXN, INF);
fill(ah, ah + MAXN, INF);
fill(arr[0], arr[0] + MAXN * MAXN, INF);
for (int i = 0, te; i < N; i++) {
string str;
cin >> str;
scanf("%d", &te);
mp[str] = i;//编号
arr[i][i] = te;
srr[i] = str;//反编号
}
scanf("%d", &M);
for (int i = 0, te; i < M; i++) {
string s1, s2;
cin >> s1 >> s2;
scanf("%d", &te);
arr[mp[s1]][mp[s2]] = arr[mp[s2]][mp[s1]] = min (te, arr[mp[s2]][mp[s1]]);
}
string s1, s2;
cin >> s1 >> s2;
dijkstra(mp[s1], mp[s2]);
int ans = dis[mp[s2]];
if (ans != INF) {
printf("%d\n", ans);
int nxt[500];
int back = mp[s2], cnt = 0;
while (back != mp[s1]) {
nxt[cnt++] = back;
back = pre[back];
}
cout<<s1;
for (int i = 0; i < cnt; i++) {
cout<<"->"<<srr[nxt[cnt - i - 1]];
}
cout<<endl;
}
else {
printf("Why not go home by plane?\n");
}
return 0;
}
