hdu 1874 最短路

http://acm.hdu.edu.cn/showproblem.php?pid=1874

最短路模板题

方法一：Floyd算法。代码超简单，用到了动态规划的思想，能计算出任意两点的最短路，计算多源最短路时很方便。只是太耗时了，小心TLE

同类型题：poj3660

#include<stdio.h>
#include<stdlib.h>
#define N 202
#define Max 2000000
int f[N][N];
void floyd(int n)
{
 int i,j,k;
 for(k=0;k<n;k++)
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
   {
    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    f[j][i]=min(f[j][i],f[j][k]+f[k][i]);
   }
}
int main()
{
 int i,j,n,m,a,b,x,s,t;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    f[i][j]=(i==j?0:Max);
   for(i=0;i<m;i++)
   {
    scanf("%d%d%d",&a,&b,&x);
    f[a][b]=f[b][a]=min(f[a][b],x);
   }
   scanf("%d%d",&s,&t);
   floyd(n);
   printf("%d\n",f[s][t]==Max?-1:f[s][t]);
 }
 return 0;
}

方法二：Dijkstra算法。效率较高，但是只能计算已知的两点间的最短路。

#include<stdio.h>
#include<string.h>
#define N 202
#define Max 2000000
//map标记任意两点距离，dist标记起点到每一点的距离，flag标记该点是否走过
int map[N][N],dist[N],flag[N];
int n,m,s,t;
void Dijkstra()
{
	int i,j,node,min;
	memset(flag,0,sizeof(flag));
	for(i=0;i<n;i++)
		dist[i]=map[s][i];
	flag[s]=1;
	for(i=0;i<n;i++){
		min=Max;
		for(j=0;j<n;j++){  //找到当前离起点最近的点(即dist最小)
			if(flag[j]==0&&dist[j]<min){
				min=dist[j];
				node=j;
			}
		}
		if(min==Max)break;
		flag[node]=1;
		for(j=0;j<n;j++){  //更新未走过的点的dist
			if(flag[j]==0&&dist[j]>dist[node]+map[node][j])
				dist[j]=dist[node]+map[node][j];
		}
	}
	return;
}
int main()
{
	int i,j,a,b,x;
	while(scanf("%d%d",&n,&m)!=EOF){
		for(i=0;i<n;i++){
			for(j=0;j<n;j++)
				map[i][j]=(i==j?0:Max);
		}
		for(i=0;i<m;i++){
			scanf("%d%d%d",&a,&b,&x);
			map[a][b]=map[b][a]=(map[a][b]<x?map[a][b]:x);
		}
		scanf("%d%d",&s,&t);
		Dijkstra();
		printf("%d\n",dist[t]==Max?-1:dist[t]);
	}
	return 0;
}