PAT【甲级】1131

题目链接：
题目简述：给定一个地铁路线，问从初始位置到终止位置的最短路径，如果有多个最短路径那么找到那条转线最少的路径。

#include<bits/stdc++.h>
using namespace std;

unordered_map<int, bool> vis;
unordered_map<int, int> whichLine;
vector<int> v[10000];
vector<pair<int,int>> turn, ans_turn;//第一维是在答案中要输出的节点，第二维是代表哪条线路
int shortest = -1;

void dfs(int beg, int dest, int paths, int pre){
    if(beg == dest){//如果到达了目的节点，总共有三种情况需要更新答案数组：1.当第一条路径被找到2.当最短路径被找到3.当换站次数最少的路径被找到
        if(shortest == -1 || (paths < shortest && shortest != -1) || (paths == shortest && ans_turn.size() - 1 > turn.size())){
            ans_turn.assign(turn.begin(), turn.end());
            ans_turn.push_back({dest, whichLine[pre * 10000 + beg]});//由于代码设计的问题，尾结点需要在这里进行插入
        } 
        shortest = paths;
        return;
    }
    if(shortest != -1 && shortest <= paths)//剪枝操作（不要用换乘站数来剪枝，是不可以剪的）
        return;
    for (int i = 0; i < v[beg].size();i++){
        if(!vis[v[beg][i]]){
            vis[v[beg][i]] = true;
            if(pre != -1 && whichLine[pre * 10000 + beg] != whichLine[beg * 10000 + v[beg][i]])
                turn.push_back({beg, whichLine[pre * 10000 + beg]});//当前节点要到另外一条路线，那么记录
            dfs(v[beg][i], dest, paths + 1, beg);
            if(pre != -1 && whichLine[pre * 10000 + beg] != whichLine[beg * 10000 + v[beg][i]])
                turn.pop_back();//归位回溯
            vis[v[beg][i]] = false;//必须要归位啊
        }
    }
}

int main(){
    int n, m, name, k, start, dest;
    cin >> n;
    for (int i = 1; i <= n;i++){
        cin >> m;
        int pre = -1;//记录上一个节点
        for (int j = 0; j < m;j++){
            cin >> name;
            if(pre != -1){
                v[pre].push_back(name);
                v[name].push_back(pre);
                whichLine[pre * 10000 + name] = whichLine[name * 10000 + pre] = i;//存储边是哪一条路线上的
            }
            pre = name;
        }
    }
    cin >> k;
    while(k--){
        cin >> start >> dest;
        shortest = -1;
        vis.clear();
        vis[start] = true;
        turn.clear();
        ans_turn.clear();
        dfs(start, dest, 0, -1);
        cout << shortest << endl;
        printf("Take Line#%d from %04d to %04d.\n", ans_turn[0].second, start, ans_turn[0].first);
        for (int i = 0; i < ans_turn.size() - 1;i++)
            printf("Take Line#%d from %04d to %04d.\n", ans_turn[i + 1].second, ans_turn[i].first, ans_turn[i + 1].first);
    }
    return 0;
}

这个题目因为边数还是比较少，不是很复杂的图，所以使用DFS会好一些【容易写】，只需记录几个变量就行了。