HDU 1874 畅通工程续 SPFA || dijkstra

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

题目大意：

给你一些点，让你求S到T的最短路径。

我只是来练习一下SPFA的

dijkstra:

#include<cstdio>
const int INF=1000000;
const int MAXN=200+10;
int n,m;
int map[MAXN][MAXN];
int dis[MAXN];
void dijkstra(int s)
{
	for(int i=0;i<n;i++)
		dis[i]=INF;

	bool vis[MAXN]={0};
	
	int cur=s;
	vis[s]=true;
	dis[s]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			if(!vis[j] && dis[cur] + map[cur][j] < dis[j])
				dis[j]=dis[cur] + map[cur][j];

		int min=INF;
		for(int j=0;j<n;j++)
			if(!vis[j] && dis[j] < min)
				min=dis[cur=j];
		vis[cur]=true;	
	}
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				map[i][j]=INF;

		for(int i=0;i<m;i++)
		{
			int from,to,dis;
			scanf("%d%d%d",&from,&to,&dis);
			if(map[from][to]>dis)
				map[from][to]=map[to][from]=dis;
		}
		int s,t;
		scanf("%d%d",&s,&t);
		dijkstra(s);
		if(dis[t]==INF)
			puts("-1");
		else
			printf("%d\n",dis[t]);
	}
	return 0;
}

#include<cstdio>
#include<queue>
using namespace std;
const int INF=1000000;
const int MAXN=200+10;
int n,m;
int map[MAXN][MAXN];
int dis[MAXN];
void SPFA(int s)
{
	for(int i=0;i<n;i++)
		dis[i]=INF;

	bool vis[MAXN]={0};
	
	vis[s]=true;
	dis[s]=0;
	
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int cur=q.front();
		q.pop();
		for(int i=0;i<n;i++)
		{
			if(dis[cur] + map[cur][i] < dis[i])
			{
				dis[i]=dis[cur] + map[cur][i];
				if(!vis[i])
				{
					q.push(i);
					vis[i]=true;
				}
			}			
		}
		vis[cur]=false;
	}
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				map[i][j]=INF;

		for(int i=0;i<m;i++)
		{
			int from,to,dis;
			scanf("%d%d%d",&from,&to,&dis);
			if(map[from][to]>dis)
				map[from][to]=map[to][from]=dis;
		}
		int s,t;
		scanf("%d%d",&s,&t);
		SPFA(s);
		if(dis[t]==INF)
			puts("-1");
		else
			printf("%d\n",dis[t]);
	}
	return 0;
}

HDU 1874 畅通工程续 SPFA || dijkstra

原文：http://blog.csdn.net/murmured/article/details/18568657