7-2 过年了，回家吧（百度之星校赛题目）
分数 30
作者 陈浩川
单位 厦门大学
小CC的家离学校有1000多公里，坐火车要数十个小时。每年春运之时，小CC总要绞尽脑汁寻找最合适的换乘路线。

小CC的换乘问题抽象如下：

地图上有N个城市，M条交通路线将城市两两相连。小CC需要经过若干条交通路线，从城市S回到城市T。途径每条交通路线都会消耗一定时间，在中转城市换乘也需要消耗一定时间，起点和终点的换乘时间不计算在内。现在请你编写程序，帮小CC规划回家的路，这条路必须是耗时最短的路径，如果有耗时相同的多条路径，选择其中换乘最少的一条。

例如，小CC要从厦门回到大同，下图是小CC回家时的线路图，图中的方块表示换乘时间，线路上的数字表示线路的旅途时间。

（本图仅作示意，不代表真实旅行时间和实际地理位置）

火车线路图.png

从图中可以看出，有多条路径可以选择，但是耗时最短的路径（耗时375）只有两条：

厦门->北京->大同，路途时间227+70，换乘时间78；
厦门->南昌->郑州->大同，旅途时间65+64+125，换乘时间40+81。
此时，小CC会选择换乘次数较少的第1条线路。

输入格式:
第一行为1个正整数N≤500，表示城市个数。

然后是N行，每行依次是城市名称和换乘时间。城市名称不超过40个字符，由大小写字母组成，换乘时间是不大于10
4
的正整数。

接下来是一个正整数M≤3N，表示交通路线条数。

接着M行，每行三个元素，依次是两个城市名称和路线耗时（不大于10
4
的正整数）。

最后一行依次给出起点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?

比赛时的代码（5/6 超时1）
1.dfs寻找图的最短路径（特殊1：图的中点的信息是字符串，并非往常的数字可以直接做下标创建邻接表）（特殊2：要求输出最短路径，巧妙实用dfs的（参数来维护路径信息 == 回溯维护路径信息））
2.这里的vector无法使用参数维护，故采用回溯的形式

#include<iostream>
#include<unordered_map>
#include<vector>
#include<cstring>
#include<string>
using namespace std;

const int N = 505, M = 3 * N;

int n, m;
unordered_map<string, int> f;//存储换成信息
unordered_map<string, bool> st;//标记
unordered_map<string, int> h;//邻接表
string e[M];
int ne[M], w[M], idx;
vector<string> v;//用来保存路径
vector<string> ve;//用来保存最短路径


void add(string a, string b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

string s, t;//起点和终点
int mi = 1e9;//记录最短路径
int sum = 500;//记录过的城市数量
void dfs(string s, int cur, int num)
{
    if (s == t)
    {
        if (cur - f[t] <= mi)
        {
            mi = cur - f[t];
            if (num < sum)
            {
                sum = num;
                ve.clear();
                for (auto x : v)
                {
                    ve.push_back(x);
                }
            }
        }
        return;
    }


    for (int i = h[s]; i != -1; i = ne[i])//遍历得idx；
    {
        string j = e[i];
        if (!st[j])
        {
            st[j] = 1;
            v.push_back(j);
            num++;
            dfs(j, cur + w[i] + f[j], num + 1);
            num--;
            v.pop_back();
            st[j] = 0;
        }

    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        string s;
        int x = 0;
        cin >> s >> x;
        f[s] = x;//记录 每个城市得换成时间
        h[s] = -1;//邻接表
        st[s] = 0;//初始化表标记
    }
    scanf("%d", &m);
    while (m--)
    {
        string s1, s2;
        int w;
        cin >> s1 >> s2 >> w;
        //cout << s1 << " " << s2 << " " << w << endl;
        add(s1, s2, w);
        add(s2, s1, w);
    }

    cin >> s >> t;
    if (s == t)
    {
        printf("%d\n",0);
        cout << s;
        return 0;
    }
    dfs(s, 0, 0);
    if (mi >= 1e9 || mi >= 1e7)
    {
        puts("Why not go home by plane?");
        return 0;
    }
    printf("%d\n", mi);
    cout << s;
    for (auto x : ve)
    {
        cout << "->" << x;
    }

    return 0;
}

dijkstra（寻找最短路径的同时+保存路径（并且是中间结点最少的））
1.双向映射，互相访问，先比上面的方式更加通俗易懂，感觉 时间更加加快
2.类比保存距离的数组，设置cnt[N]，记录从起点出发到i的结点个数（不包含起点，包含终点）

#include<iostream>
#include<unordered_map>
#include<string>
#include<cstring>
#include<vector>
using namespace std;


const int N = 505, M = 3 * N + 10, inf = 0x3f3f3f3f;

int n, m;
unordered_map<string, int> sti;
unordered_map<int, string> its;
int ht[N];
int h[N], e[M], w[M], ne[M], idx;
int st[N];//标记
int d[N];
int cnt[N];//记录经过的节点数
int pre[N];//记录路径的标号

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra(int u, int v)
{
    memset(d, 0x3f, sizeof d);
    d[u] = 0;

    pre[u] = 0;//起点前驱节点设为0

    for (int i = 1; i <= n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!st[j] && (t == -1 || d[j] < d[t]))
            {
                t = j;
            }
        }

        st[t] = 1;

        for (int j = h[t]; j != -1; j = ne[j])
        {
            int k = e[j];//结点k
            if (d[t] + w[j] + ht[k] < d[k])//更新
            {
                //cout << " ---" << endl;
                d[k] = d[t] + w[j] + ht[k];
                cnt[k] = cnt[t] + 1;
                pre[k] = t;//只要有更短的，直接覆盖并更新即可，最后保留的即为最短路径
            }
            else if (d[t] + w[j] + ht[k] == d[k])//路径相同的情况下，选取中间结点最少的，此时没必要更新最短举例，只是更换不同路径
            {
                if (cnt[t] + 1 < cnt[k])
                {
                    cnt[k] = cnt[t] + 1;
                    pre[k] = t;
                }
            }
        }
    }

    if (d[v] == inf)
    {
        return -1;
    }
    else
    {
        return d[v];
    }
}



int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        string s;
        int t;
        cin >> s >> t;
        sti[s] = i;
        ht[i] = t;//记录站点换成时间
        its[i] = s;
    }
    scanf("%d", &m);
    memset(h, -1, sizeof h);
    while (m--)
    {
        string a, b;
        int w;
        cin >> a >> b >> w;
        int i = sti[a], j = sti[b];
        add(i, j, w);
        add(j, i, w);
    }

    string s, t;
    cin >> s >> t;
    int u = sti[s], v = sti[t];

    int f = dijkstra(u, v);

    if (f == -1)
    {
        puts("Why not go home by plane?");
    }
    else
    {
        cout << d[v] - ht[v] << endl;//去掉终点的换成时间
        vector<string> way;
        for (int i = v; i != u; i = pre[i])//从终点到起点的下一个
        {
            way.push_back(its[i]);
        }
        cout << its[u];
        for (int i = way.size() - 1; i >= 0; i--)
        {
            cout << "->" << way[i];
        }
    }

    return 0;
}