畅通工程续

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 23792    Accepted Submission(s): 8375

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

2
-1

算法步骤：实质上广搜，从起点搜索到其他点的最短路，若某个点的距离被更新，则

那么通过这个点其他点也可能被更新。直至队列为空，算法结束。

#include"stdio.h"
#include"string.h"
#include"queue"
#include"iostream"
using namespace std;
#define N 205
const int Inf=1<<30;
int dis[N],visit[N],n;
int map[N][N];
void spfa(int s)
{
	queue<int>q;
	int i;
	for(i=0;i<n;i++)
		dis[i]=Inf;
	dis[s]=0;           
	memset(visit,0,sizeof(visit));
	q.push(s);
	while(!q.empty())
	{
		s=q.front();  //取队首元素
		q.pop();          //删除队首元素
		visit[s]=0;       //已经不在队列
		for(i=0;i<n;i++)
			if(dis[i]>dis[s]+map[s][i])
			{
				dis[i]=dis[s]+map[s][i];
				if(!visit[i])    //如果该点现在不在队列，则加入队列
				{
					q.push(i);        
					visit[i]=1;
				}
			}
	}
}
int main()
{
    int m,i,j,a,b,x,s,t;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		for(i=0;i<n;i++)     //初始化距离
			for(j=0;j<n;j++)
				map[i][j]=(i==j?0:Inf); 
		while(m--)
		{
			scanf("%d%d%d",&a,&b,&x);
			if(map[a][b]>x)
				map[a][b]=map[b][a]=x;
		}
		scanf("%d%d",&s,&t);
		spfa(s);
		if(dis[t]==Inf)
			printf("-1\n");
		else
			printf("%d\n",dis[t]);
	}
    return 0;
}

hdu 1874 畅通工程续,布布扣,bubuko.com

hdu 1874 畅通工程续

原文：http://blog.csdn.net/u011721440/article/details/21538817