题目摘要：输入地铁各线路信息，然后再输入起始站和终点站，要求打印出最佳的乘坐路线（首先乘坐站数最少，再换乘最少）；
方法：用邻接矩阵存储无向图信息，深度优先遍历进行路径搜寻，更新最优解
题目介绍如下：
#include<cstring> #include<cstdio> #include<cstdlib> #include<vector> using namespace std; const int maxn=10000; vector<int>state[maxn];//存储与state[i]站点相邻的站点 int line[maxn][maxn]; int vis[maxn*maxn]; int minstep,mintrans;//最小站数,最小换乘数 //int steps,trans;//当前路径累计步数和换乘数,用path可求 vector<int>ans;//存储得到的路径最优解 vector<int>path;//存储搜索过程的路径 int caltrans(vector<int> p){//容器传参 int num=0; for(int i=1;i<p.size()-1;i++){ if(line[p[i-1]][p[i]]!=line[p[i]][p[i+1]]) num++; } return num; } void dfs(int start,int finish){ vis[start]=1;//进来先标记该结点正被遍历 //printf("**%d %d",start,finish); path.push_back(start); if(finish == start){ // printf("?相等过 "); if(path.size()<minstep||(path.size()==minstep&&caltrans(path)<mintrans)){ mintrans=caltrans(path); minstep=path.size(); ans=path; } } for(int i=0;i<state[start].size();i++){ if(vis[state[start][i]]==0){//条件是== 0 dfs(state[start][i],finish);//递归遍历 } } //回溯 vis[start]=0; path.pop_back(); } int main(){ int n; scanf("%d",&n); int m,pre,cur; for(int i=1;i<=n;i++){//存储地铁线路图信息，包括相邻站信息和任意两站之间的线路的信息 scanf("%d %d",&m,&pre); for(int j=0;j<m-1;j++){//边界m-1 scanf("%d",&cur); state[pre].push_back(cur);//无向图所以需要存储两次 state[cur].push_back(pre); line[pre][cur]=i;//存储站之间的线路信息 line[cur][pre]=i;//存储站之间的线路信息 pre=cur; } } int q; scanf("%d",&q); while(q--){ int start,finish; scanf("%d %d",&start,&finish); memset(vis,0,sizeof(vis)); minstep=mintrans=maxn; path.clear(); // trans=steps=0;//用path就可实现 dfs(start,finish); printf("%d ",ans.size()-1);//-1因为不包括起始站； int curline = line[ans[0]][ans[1]];//开始线号 int pre = ans[0];//每条换乘线的起始站 for(int i=0;i<ans.size()-1;i++){//有几条线路需要打印 if(curline!=line[ans[i]][ans[i+1]]){ printf("Take Line#%d from %d to %d. ",curline,pre,ans[i]); pre=ans[i]; curline=line[ans[i]][ans[i+1]]; } } //打印最后一条线路 printf("Take Line#%d from %d to %d. ",curline,pre,ans.back()); } return 0; }
解题关键：
1 用state[i][j]存储i站的相邻站j
2 dfs搜索图时，注意回溯
3 理解dfs的过程。执行dfs(start,finish)语句时，不断递归进行；递归结束时，全部站点均遍历过，同时将最优解存储在ans和minstep中