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;
}