题目粗心：

给一个无向图，求出从一点到另外一点的最短门路，这里的最短，指的是从终点到起点所经验的点的数目起码，如果有多条，输入中转站点起码的。

算法思路：

一开始想到的是用Dijkstra算法求解该问题，然而Dijkstra算法更适宜求解第一标尺为边权相干问题，所以想到了DFS，并设置其参数depth,用来记录在从终点到起点的遍历过程中所经验的结点个数，而后采纳全局量minDepth保留最小的depth,为了不便判断是否是直达结点问题，应用邻接矩阵存储两个连贯的点的边对应的线路，比方2000与2001连通，该边是Line# 4的一部分，则G[2000][2001]=4;应用全局变量$minTranNum$记录乘坐的起码线路数目。

DFS遍历办法：

DFS函数中设置参数为以后结点st,起点e和深度depth,应用vector<int> result保留最优的门路,vector<int> path暂存以后门路, 首先拜访以后节点(保留到path中，并设置拜访标记为true)，而后判断是否达到起点，如果是，首先计算以后门路的直达节点数目，这里的计算方法是应用一个set汇合$diffLines$增加所有的 线路，其大小就是乘坐的线路数目(其大小减一就是直达节点数目)，如果minDepth>depth阐明以后门路更短，那么就更新最优门路和最优间隔和乘坐线路数目,如果 长度雷同然而乘坐的线路起码，那么更新最优门路和乘坐线路数目，最初回溯。如果没有达到起点，就递归遍历每一个没有拜访的领接点，如果所有的领接点都曾经拜访结束， 那么就回溯。

留神点：

  • 1、每一次查问都得将全局变量minDepth，minTranNum，visited初始化。
  • 2、如果程序没有报错，没有输入后果，查看是否DFS函数有回退操作(path.pop_back(),visited[st]=false)

提交后果：

AC代码：

#include<cstdio>#include<vector>#include<unordered_set>#include<cstring>using namespace std;int G[10000][10000];//G[i][j]=4示意i和j相连接的边在第4条地铁上vector<int> path;// 暂存以后搜寻到的门路vector<int> result;// 最优门路vector<int> Adj[10000];// 邻接表bool visited[10000];int minDepth;// 最短长度int minTranNum;//乘坐的起码线路数目void DFS(int st, int e, int depth){    // 首先拜访以后节点    path.push_back(st);    visited[st] = true;    if(st == e){        // 达到起点        // 计算乘坐的线路数目        unordered_set<int> diffLines;// 不同的线路数目        for (int i = 0; i < path.size() - 1; ++i) {            diffLines.insert(G[path[i]][path[i+1]]);        }        if(minDepth>depth){            // 以后门路更短            result = path;            minDepth = depth;            minTranNum = diffLines.size();        } else if(minDepth==depth&&minTranNum>diffLines.size()){            // 长度雷同,然而直达次数起码            result = path;            minTranNum = diffLines.size();        }        // 回溯        path.pop_back();        visited[st] = false;        return;    }    // 拜访每一个领接点    for (int next : Adj[st]) {        // 领接点        if(!visited[next]){            DFS(next, e, depth + 1);        }    }    path.pop_back();// 回溯    visited[st] = false;}void print(int start,int end){    printf("%d\n",minDepth);    int current_line = G[result[0]][result[1]];// 以后线路    int s = start;// 乘坐以后线路的终点    for (int i = 1; i < result.size()-1; ++i) {        if(G[result[i]][result[i+1]]!=current_line){            // i为换乘站            printf("Take Line#%d from %04d to %04d.\n",current_line,s,result[i]);            s = result[i];            current_line = G[result[i]][result[i+1]];        }    }    // 始终没有换乘或者以后位最初一次直达地铁线    printf("Take Line#%d from %04d to %04d.\n",current_line,s,end);}int main(){    int N;    scanf("%d",&N);    for (int i = 0; i < N; ++i) {        int M;        scanf("%d",&M);        int a,b;        for (int j = 0; j < M; ++j) {            if(j==0){                scanf("%d",&a);            } else {                scanf("%d",&b);                G[a][b] = G[b][a] = i+1;                Adj[a].push_back(b);                Adj[b].push_back(a);                a = b;            }        }    }    int K;    scanf("%d",&K);    int start,end;    for (int k = 0; k < K; ++k) {        scanf("%d %d", &start, &end);        // 每次查问都得初始化        minDepth = 0x3fffffff;        minTranNum = 0x3fffffff;        memset(visited,0, sizeof(visited));        path.clear();        result.clear();        DFS(start, end, 0);        print(start, end);// 输入出行计划    }    return 0;}