POJ 2387 Til the Cows Come Home（Dijkstra算法）

http://poj.org/PRoblem?id=2387

  最短路的简单问题   套模板 运用Dijkstra算法即可  不过要注意重边问题  即 两点之间可能会有多条直接连通的路 因为我们求最短路 所以只把这多条路中最短的一条记录下来即可

代码如下:

#include <stdio.h>int map[2010][2010];int dis[2010];int maxinf=999999999;void Dijkstra(int n){ 	int vis[2010]; 	for (int i=1;i<=n;i++)	 { 		dis[i]=map[1][i]; 		vis[i]=0;	 }	  	vis[1]=1; 	dis[1]=0; 	 	int u; 	for (int i=1;i<=n;i++){ 		int mindis=maxinf; 		for (int j=1;j<=n;j++){ 			if (!vis[j]&&dis[j]<mindis){ 				u=j; 				mindis=dis[j];			 }			 		 } 		  		vis[u]=1; 		 		for (int j=1;j<=n;j++){ 			if (!vis[j]&&dis[u]+map[u][j]<dis[j]){ 				dis[j]=dis[u]+map[u][j];			 }		 } 			 }  	 }int main (){	int N,M;	int A,B,C;	scanf ("%d%d",&N,&M);	 	for (int i=1;i<=M;i++){	 		for (int j=1;j<=M;j++){	 				map[i][j]=maxinf;			 }		 } 		 for (int i=1;i<=N;i++){		 	scanf ("%d%d%d",&A,&B,&C);		 	if (map[A][B]>C)//注意重边 			 {		 		map[A][B]=C;		 		map[B][A]=C;				 }		 }		 Dijkstra(M); 		 printf ("%d/n",dis[M]);		return 0;}