题意：

有N个点，给出从a点到b点的距离，当然a和b是互相可以抵达的，问从1到n的最短距离

分析：

典型的模板题，但是一定要注意有重边，因此需要对输入数据加以判断，保存较短的边，这样才能正确使用模板。

题解

#include<iostream>#include<Queue> #include<cstdio>#include<vector>#include<string.h> using namespace std;#define maxn 2001#define inf 0x3f3f3fint map[maxn][maxn];int dist[maxn];bool visited[maxn];typedef pair<int,int> P;void dijkstra(int s,int n){	priority_queue<P,vector<P>,greater<P> > Q;	memset(visited,0,sizeof(visited));	for(int i=1;i<=n;i++){		dist[i]=inf;	}	dist[s]=0;	Q.push(P(0,s));		while(!Q.empty()){			int v=Q.top().second;		Q.pop();		if(visited[v]) continue;		visited[v]=true;		for(int i=1;i<=n;i++){			int len=dist[v]+map[v][i];			if(dist[i]>len){				dist[i]=len;				Q.push(P(len,i));			}		}	}	}int main(){	int n,t;	while(scanf("%d %d",&t,&n)!=EOF){		for(int i=1;i<=n;i++){			for(int j=1;j<=n;j++){				map[i][j]=(i==j?0:inf);			}		}		while(t--){			int b,c,d;			scanf("%d %d %d",&b,&c,&d);			if(map[b][c]>d){				map[b][c]=d;				map[c][b]=d;			}		}		dijkstra(n,n);		printf("%d\n",dist[1]);	} } 

POJ - Til the Cows Come Home(Dijkstra)