畅通工程续

3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2

2
-1

解题思路：裸的Dijkstra算法，求正权最短路，这题要注意的是，两点之间可能存在多条长度不同的路，建图时注意取最短的一条。

代码如下：

#include <cstdio>
#include <cstring>
#define inf 1e9
const int maxn=205;
int eg[maxn][maxn],dist[maxn],s[maxn];
int n,m,st,ed;
void Dijkstra()
{
	memset(s,0,sizeof(s));
	for(int i=0;i<n;i++)
		dist[i]=eg[st][i];
	s[st]=1;
	dist[st]=0;
	for(int i=0;i<n;i++)
	{
		int u,mi=inf;
		for(int j=0;j<n;j++)
		{
			if(!s[j]&&mi>dist[j])
			{
				u=j;
				mi=dist[j];
			}
		}
		s[u]=1;
		for(int j=0;j<n;j++)
		{
			if(!s[j]&&dist[j]>dist[u]+eg[u][j])
				dist[j]=dist[u]+eg[u][j];
		}
	}
}
int main()
{
	int a,b,c;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				eg[i][j]=inf;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			if(eg[a][b]>c)
				eg[a][b]=eg[b][a]=c;
		}
		scanf("%d%d",&st,&ed);
		Dijkstra();
		if(dist[ed]==inf)
			printf("-1\n");
		else
			printf("%d\n",dist[ed]);
	}
}

hdu 1874 畅通工程续 (裸的 Dijkstra)

原文：http://blog.csdn.net/criminalcode/article/details/47337639