城市地图

暑假小哼想到去小哈家里去玩，小哼和小哈住在不同的城市，并且小哼之前从来没有去过小哈家，这是小哼第一次上门。怎么办呢？小哼便想起了百度地图。百度地图一下子就给出了从小哼家到小哈家的最短行车方案。爱思考的小哼想知道百度地图是如何计算出最短行车距离的。下面是城市的地图：

输入

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
第一行的5表示5个城市，8表示8条公路。
接下来8行每行3个数a,b,c，表示城市a到城市b有一条长为c的路。（注意是单程的）。

输出

输出小哼（1号点）到小哈（5号点）的最短路程

示例

输入：
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

代码

#include<bits/stdc++.h>
using namespace std;
int a[100][100],book[100];
int step=INT_MAX,m,n;
void dfs(int cur,int dis)
{
	if(cur==n)
	{
		if(dis<step)
			step=dis;
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(!book[i]&&a[cur][i]!=INT_MAX)
		{
			book[i]=1;
			dfs(i,dis+a[cur][i]);
			book[i]=0;
		} 
	}
}
int main()
{
	int b,c,d;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(i==j)
				a[i][j]=0;
			else
				a[i][j]=INT_MAX; 
	for(int i=1;i<=m;i++)
	{
		cin>>b>>c>>d;
		a[b][c]=d;
		book[1]=1;
		dfs(1,0);
	}
	cout<<step<<endl;
	return 0;
}