【B006】50136142WXY的坑爹百度地图【难度B】——————————————————————————————————————————————————————————————————————————
【题目要求】
输出描述的链接 and其他说明的链接 社团里的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
【输出要求】
*还是就一个数，不知知道是什么的按前面的链接。
【输出示例】
9
【其它要求】
LJX认为N与M不会太大（点击前面的链接查看什么叫不会太大）
【试题分析】
这个问题由于要求很宽松，所以这里不再使用最短路算法进行计算，我们使用把每条路经常遍历的算法计算，也就是DFS深度优先遍历的思想。
我们在脑海里构成一个表，把这张图放进表里，根据有5行5列，比如（1,1）=0代表从1号城市到1号城市的距离是0，对于2号城市到4号城市没有路径的情况我们用9999999（这里认为9999999是无限大）填充。即（2,4）=9999999。
知道了这些，我们就可以开始求最短路径了，我们规定一个规则，当遇到路口时先往标号小的城市那边走，比如我们从1号城市出发，可以到达2号与5号城市，根据规则，转向2号城市。以此类推，第一次遍历的路径是1-2-3-4-5，但谁说这就是最短的了？所以我们在退回4号城市尝试其它路径。
就这样我们在设置一个变量对最短路不断更新即可，是不是很简单，下面是代码。
【代码】
#include<iostream>
#include<cstdio>
using namespace std;
int minn=9999999,book[101],n,e[101][101];
void dfs(int cur,int dis)
{
int j;
if(dis>minn) return ;
if(cur==n)
{
if(dis<minn) minn=dis;
return ;
}
for(j=1;j<=n;j++)
{
if(e[cur][j]!=9999999 && book[j]==0)
{
book[j]=1;
dfs(j,dis+e[cur][j]);
book[j]=0;
}
}
return;
}
int main()
{
int i,j,m,a,b,c;
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j) e[i][j]=0;
else e[i][j]=9999999;
}
}
for(i=1;i<=m;i++)
{
cin>>a>>b>>c;
e[a][b]=c;
}
book[1]=1;
dfs(1,0);
cout<<minn;
//system("pause");
return 0;
}