50136142WXY的坑爹百度地图

试题描述

社团里的WXY童鞋今天要出去旅游啦（他现在在北京为1号城市），决定去朝鲜平壤（N号城市）装逼。但是很穷的WXY没有钱坐飞机，只好坐汽车去朝鲜了。但是车上的百度地图十分不给力，每回不是把WXY带到了山顶上就是带到了下水道里（WXY的车能开进下水道，真是666666）。WXY被百度导航整得苦不堪言。还好WXY大神事先准备了一张有N个节点，M条公路的只有火星人才能看懂的图。作为大神的WXY才懒得去计算这么简单的问题呢，所以他强制你帮他计算从北京到平壤的最短路径是什么。（否则你就会被WXY打死.快开始计算吧。）

输入

*第一行：两个数N与M代表有N个城市，M条公路。
*接下来的M行：每行有三个数a,b,c代表城市a,b之间有一条长度为c的公路。

输出

*还是就一个数，不知道是什么的按前面的链接。

输入示例

5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3

输出示例

其他说明

N,M<=50

本道题是一道DFS的题。

如图是输入实例的邻接矩阵，可结合代码中注释理解。∞是正无穷

 1 //本题是处理有向图的问题，用深度搜索 
 2 #include <iostream>
 3 
 4 using namespace std;
 5 int e[101][101],minn=66666666;  //e记录 i 到 j 有没有一条路径 （有的话记录距离，没有的话正无穷） 
 6 int n,m;
 7 bool book[101];   //book记录已走过的路径，防止类似于‘1-2-3-1’的死循环 
 8 void dfs(int cur,int dis)   //cur记录城市编号，dis是距离  （void表示没有返回值） 
 9 {
10     if(dis>minn) return ;  //如果当前距离已经大于最小值，就没有必要往下找了 
11     if(cur==n)   //到达目的地 
12     {
13         if(dis<minn) minn=dis;  //更新minn值 
14         return ;
15     }
16     for(int i=1;i<=n;i++)
17     {
18         if(e[cur][i]!=66666666 && book[i]==0)   //当前城市和 i 城市 之间有路径，且i城市没有走过 
19         {
20             book[i]=1;   //标记为走过 
21             dfs(i,dis+e[cur][i]);  //继续深搜 
22             book[i]=0;   //进行下一次深搜前，所有路径都没有经过过 
23         }
24     }
25     return ;
26 }
27 int main()
28 {
29     scanf("%d%d",&n,&m);
30     for(int i=1;i<=n;i++)
31         for(int j=1;j<=n;j++)
32             if(i==j) e[i][j]=0;  //自己到自己距离为0 
33             else e[i][j]=66666666;  //否则初始化为正无穷 
34     for(int i=1;i<=m;i++)  //输入路径 
35     {
36         int a,b,c;
37         scanf("%d%d%d",&a,&b,&c);
38         e[a][b]=c;
39     }
40     book[1]=1;  //当前位置已经走过 
41     dfs(1,0);
42     printf("%d",minn);
43     //system("pause");
44     return 0;
45 }

50136142WXY的坑爹百度地图