HPUOJ---2017寒假训练--专题3/A-Til the Cows Come Home（最短路-dijkstra）

A - Til the Cows Come Home

5 51 2 202 3 303 4 204 5 201 5 100Sample Output
90HintINPUT DETAILS: There are five landmarks. OUTPUT DETAILS: Bessie can get home by following trails 4, 3, 2, and 1.
#include<cstdio>#define MAX 999999999int dp[1111][1111];int dis[1111];int vis[1111];int T,N,st,ed;int min(int a,int b){	return (a<b)?a:b;}void init(){	for(int i=1;i<=N;i++)	{		dis[i]=MAX;		vis[i]=0;		for(int j=1;j<=N;j++)		   dp[i][j]=dp[j][i]=MAX;	}}void dijkstra(){	dis[st]=0;	while(1)	{		int v=-1;		for(int i=1;i<=N;i++)		{			if(!vis[i]&&(v==-1||dis[i]<dis[v]))			    v=i;		}		if(v==-1)		    break;		vis[v]=1;		for(int i=1;i<=N;i++)		{			if(dis[i]>(dis[v]+dp[v][i]))			   dis[i]=dis[v]+dp[v][i];		}	}}int main(){	scanf("%d%d",&T,&N);	init();	while(T--)	{		int a,b,c;		scanf("%d%d%d",&a,&b,&c);		dp[a][b]=dp[b][a]=min(c,dp[a][b]);	}	st=1;	ed=N;	dijkstra();	PRintf("%d/n",dis[ed]);	return 0;}