题目链接：点击打开链接
题目大意：找出一条路线，使得对任何给定的起点和终点，可以找出中途经停站最少的路线；如果经停站一样多，则取需要换乘线路次数最少的路线。
解题思路：一遍DFS即可～DFS过程中要维护两个变量：minCnt-中途经停的最少的站; minTransfer-需要换乘的最小次数～
- 可以这样计算出一条线路的换乘次数：在line[10000][10000]的数组中保存每两个相邻站中间的线路是几号线～从头到尾遍历最终保存的路径，preLine为前一小段的线路编号，如果当前的结点和前一个结点组成的这条路的线路编号和preLine不同，说明有一个换乘，就将cnt+1，最后遍历完累加的cnt即是换乘的次数～
- update：由于新的PAT系统中会显示原解法有一个测试用例内存超限，考虑到line[10000][10000]存储的方式太暴力了，所以将line换成了unordered_map<int, int> line存储的方式，第一个int用来存储线路，每次将前四位存储第一个线路，后四位存储第二个线路，使用a[i-1]*10000+a[i]的方式存储，第二个int用来保存两个相邻中间的线路是几号线～
- 可以这样计算出一条线路中途停站的次数：在dfs的时候有个变量cnt，表示当前路线是所需乘的第几个站，每次dfs时候将cnt+1表示向下遍历一层～cnt就是当前中途停站的次数～
- 可以这样输出结果：和计算线路换乘次数的思路一样，每当preLine和当前Line值不同的时候就输出一句话～保存preTransfer表示上一个换乘站，最后不要忘记输出preTransfer和最后一个站之间的路即使最后一个站并不是换乘站～。
- 有时候，全局变量对 DFS 是禁忌，特别是每次回溯时需要变回起初的值的变量，如果用全局替代局部变量的话，一旦改变就回不去起初的“还原点”了。
AC 代码
usingnamespacestd; typedeflonglongll; constintmaxn=1e4+10; intd, id; intminCnt, minTran; intvis[maxn]; unordered_map<int,int>line; vector<int>tpath, path, v[maxn]; intfhash(intid1,intid2) { returnid1*10000+id2; } intcalTran() { intpreline=0, cnt=-1; for(inti=1;i<tpath.size();i++) { id=fhash(tpath[i-1],tpath[i]); if(line[id]!=preline) cnt++, preline=line[id]; } returncnt; } voiddfs(ints, intcnt) { if(s==d&& (cnt<minCnt||cnt==minCnt&&calTran()<minTran)) { path=tpath; minCnt=cnt; minTran=calTran(); } if(s==d) return; for(inti=0;i<v[s].size();i++) { inttid=v[s][i]; // 去掉 int dfs最终答案会出问题，因为当 tid 作为全局变量时，一直在变，而局部变量对dfs的一个很大的作用就是每次回溯时，该变量的值可以恢复到起初的值if(!vis[tid]) { vis[tid]=1; tpath.push_back(tid); dfs(tid, cnt+1); vis[tid]=0; tpath.pop_back(); } } } intmain() { intn,m,pre,q,s; scanf("%d",&n); for(inti=1;i<=n;i++) { scanf("%d%d",&m,&pre); for(intj=1;j<m;j++) { scanf("%d",&id); v[pre].push_back(id); v[id].push_back(pre); line[fhash(pre,id)]=line[fhash(id,pre)]=i; pre=id; } } scanf("%d",&q); while(q--) { scanf("%d%d",&s,&d); mem(vis,0), tpath.clear(), minCnt=minTran=INF; vis[s]=1; tpath.push_back(s); dfs(s,0); tpath.pop_back(); vis[s]=0; printf("%d\n",minCnt); intpreline=0, len=path.size(), preTran; for(inti=1;i<len;i++) { id=fhash(path[i-1],path[i]); if(line[id]!=preline) { if(preline!=0) printf("Take Line#%d from %04d to %04d.\n",preline,preTran,path[i-1]); preline=line[id]; preTran=path[i-1]; } } printf("Take Line#%d from %04d to %04d.\n",preline,preTran,path[len-1]); } return0; }
