题目：click me~
题意：给出几条地铁线路，查询从起点站到终点站的经停次数最少的路线，如果经停次数相同，输出换乘次数最少的路线。
解题思路：需要一遍DFS，DFS中要维护两个变量：mincnt中途经停最少的次数，mintransfer需要换乘的最小次数
步骤一：计算换乘次数的方法：在line[10000][10000]的数组中保存每两个相邻站中间的路是几号线。从头到尾遍历最终的路径，preline是前一小段的线路编号，若当前小段的线路编号与preline不同，说明有一个换乘，累加器加1；
步骤二：计算经停次数的方法：在DFS时设置一个cnt，表示当前站是路线中的第几个站，每次向下遍历一层就将cnt+1；
步骤三：输出结果的方法：和计算换乘次数的思路一样，遍历最终的路径，若当前line值与preline不同，输出一句话，用pretransfer保存上一个经停站。
code
#include<iostream> #include<vector> #include<unordered_map> using namespace std; vector<vector<int>> v(10000); int vis[10000], mincnt, mintransfer, st, ed; unordered_map<int, int> line; vector<int> path, temppath; int transfercnt(vector<int> a) { int cnt = -1, preline = 0; for (int i = 1;i < a.size();i++) { if (line[a[i - 1] * 10000 + a[i]] != preline)cnt++; preline = line[a[i - 1] * 10000 + a[i]]; } return cnt; } void dfs(int node, int cnt) { if (node == ed && (cnt < mincnt || (cnt == mincnt && transfercnt(temppath) < mintransfer))) { mincnt = cnt; mintransfer = transfercnt(temppath); path = temppath; } if (node == ed)return; for (int i = 0;i < v[node].size();i++) { if (vis[v[node][i]] == 0) { vis[v[node][i]] = 1; temppath.push_back(v[node][i]); dfs(v[node][i], cnt + 1); vis[v[node][i]] = 0; temppath.pop_back(); } } } int main() { int n, m, k, pre, temp; cin >> n; for (int i = 0;i < n;i++) { cin >> m >> pre; for (int j = 1;j < m;j++) { cin >> temp; v[pre].push_back(temp); v[temp].push_back(pre); line[pre * 10000 + temp] = line[temp * 10000 + pre] = i+1; pre = temp; } } cin >> k; for (int i = 0;i < k;i++) { cin >> st >> ed; mincnt = 99999, mintransfer = 99999; temppath.clear(); temppath.push_back(st); vis[st] = 1; dfs(st, 0); vis[st] = 0; cout << mincnt << endl; int preline = 0, pretransfer = st; for (int j = 1;j < path.size();j++) { if (line[path[j - 1] * 10000 + path[j]] != preline) { if (preline != 0)printf("Take Line#%d from %04d to %04d.\n", preline, pretransfer, path[j - 1]); preline = line[path[j - 1] * 10000 + path[j]]; pretransfer = path[j - 1]; } } printf("Take Line#%d from %04d to %04d.\n", preline, pretransfer, ed); } system("pause"); return 0; }
