Til the Cows Come Home(简单的最短路)

Til the Cows Come Home
Bessie 在外地，想要在 Farmer John 叫醒她早上挤奶之前回到谷仓尽可能多地睡觉。Bessie 需要她的美容觉，所以她想尽快回来。

Farmer John 的田地中有 N (2 <= N <= 1000) 个地标，唯一编号为 1…N。地标 1 是谷仓；Bessie 整天站立的苹果树树林是 N 的地标。奶牛使用 T (1 <= T <= 2000) 条地标之间不同长度的双向牛道在田间行进。Bessie 对自己的导航能力没有信心，所以一旦开始，她总是从头到尾留在一条小路上。

给定地标之间的小径，确定 Bessie 必须步行才能返回谷仓的最小距离。保证存在一些这样的路由。
输入

• 第 1 行：两个整数：T 和 N

• 第 2…T+1 行：每行将一条路径描述为三个空格分隔的整数。前两个整数是路径经过的地标。第三个整数是路径的长度，范围是 1…100。
  输出

• 第 1 行：单个整数，即 Bessie 从地标 N 到地标 1 必须经过的最小距离。
  样本输入
  5 5
  1 2 20
  2 3 30
  3 4 20
  4 5 20
  1 5 100
  样本输出
  90
  暗示
  输入细节：

有五个地标。

输出详细信息：

Bessie 可以沿着路径 4、3、2 和 1 回家。
思路：简单的迪杰斯特拉，不过可能有一个坑，如本来给出
x y 2，后面又给出，x y 20，即重边问题。

#include <cstdio>
#include <queue>
#include <climits>
#include <string.h>
#include <iostream>
using namespace std;
int vist[1005];
int dis[1005];
int e[1005][1005];
int main()
{
	int n,m,x,y,zhi,inf,i;
	while(cin>>m>>n){
		memset(vist,0,sizeof(vist));
		memset(e,0x3f3f3f,sizeof(e));
		inf=e[0][0];
		for(i=1;i<=m;i++){
			scanf("%d%d%d",&x,&y,&zhi);
			if(zhi<e[x][y]){//如果遇到重边，选择最小的边
			e[x][y]=zhi;
			e[y][x]=zhi;
			}	
		}
		for(i=1;i<=n;i++){//dis[i]保存的是起点到i点的最短距离
			dis[i]=e[1][i];
		}
		int cnt=0,d,xiao;
		cnt++;
		vist[1]=1;
		while(cnt<n){//n个点只需要选n-1条边
			xiao=inf;
			d=-1;
			for(i=1;i<=n;i++){
				if(!vist[i]&&xiao>dis[i]){//选则起点到i点最小的边
					xiao=dis[i];
					d=i;
				}
			}
			if(d==-1) break;
			cnt++;
			vist[d]=1;//标记这个点已经选了
			for(i=1;i<=n;i++){
				if(!vist[i]&&e[d][i]+dis[d]<dis[i]){//通过d点到i的距离比直接到i的距离小，所以更新
					dis[i]=e[d][i]+dis[d];
				}
			}
		} 
		printf("%d\n",dis[n]);
	
	}
}