50136142WXY的百度地图

50136142WXY的百度地图

【试题描述】

     社团里的WXY童鞋今天要出去旅游啦（他现在在北京为1号城市），决定去朝鲜平壤（N号城市）。但是很穷的WXY没有钱坐飞机，只好坐汽车去朝鲜了。但是车上的百度地图十分不给力，每回不是把WXY带到了山顶上就是带到了下水道里（WXY的车能开进下水道，真是666666）。WXY被百度导航整得苦不堪言。还好WXY大神事先准备了一张有N个节点，M条公路的只有火星人才能看懂的图。作为大神的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

【其他说明】

M,N均小于50

【试题分析】

这道题，额，我认为不用太多的解释，真的如LJX李家鑫所说：“可以喝的超大桶水”，按照图论传统做法套就行，来，直接看代码吧！

【代码】

#include<iostream>
using namespace std;
int minn=99999999,book[101],n,e[101][101];//e数组储存长度，如果到达不了就是inf
void dfs(int cur,int dis)
{
	int j;
	if(dis>minn) return ;//已经遍历完了
	if(cur==n)//当遍历完所有路径了，cur就等于n
	{
		if(dis<minn) minn=dis;//更新了最大值
		return ;//满足条件返回
	}
	for(j=1;j<=n;j++)
	{
		if(e[cur][j]!=99999999&&book[j]==0)//有路径到达，且没有走过此条路
		{
			book[j]=1;//标记为已走过
			dfs(j,dis+e[cur][j]);//dis加上此路径的长度
			book[j]=0;//恢复标记
		}
	}
	return ;//已结束，返回
}
int main()
{
	int i,j,m,a,b,c;
	scanf("%d%d",&n,&m);//输入n和m
	for(i=1;i<=n;i++)
	    for(j=1;j<=n;j++)
	        if(i==j) e[i][j]=0;//i等于j表示同一点
	        else e[i][j]=99999999;//到达不了
    for(i=1;i<=m;i++)
    {
    	scanf("%d%d%d",&a,&b,&c);
    	e[a][b]=c;//路径a，b权值为c
	}
	book[1]=1;//点一标为已走
	dfs(1,0);//从1开始dfs
	printf("%d",minn);//输出
}