最短路 队长：北大d题.txt

ACM资料大集合

X-Ray(361096807) 08:29:24
昨天北大比赛最短路题的代码:

#include <cstdio>
#include <vector>
#include <queue>
#include <list>

using namespace std;

const int N = 1010;

int dis[N];
int tmp[N]; 
int n,m;

vector< list< pair<int,int> > >ad;

int SPFA(int src,int des)
{
	bool st[N] = {false};
	int i,j,k;
	queue<int>q;

	for(i=1;i<=n;i++) dis[i] = 10000000;
	dis[src] = 0;
	q.push(src); st[src] = true;
	while(!q.empty())
	{
		i = q.front();
		q.pop();
		list< pair<int,int> >::iterator it;
		for(it = ad[i].begin(); it != ad[i].end(); it++)
		{
			j = it->first;
			k = it->second;
			if(dis[i]+k<dis[j])
			{
				dis[j] = dis[i] + k;
				if(!st[j]) { st[j] = true; q.push(j); }
			}
		}
		st[i] = false;
	}
	return dis[des];
}

int main()
{
	int i,j,k,src;

	scanf("%d%d%d",&n,&m,&src);
	ad.resize(n+1);
	for(;m;m--)
	{
		scanf("%d%d%d",&i,&j,&k);
		ad[i].push_back(make_pair(j,k));
	}

	SPFA(src,src);
	for(i=1;i<=n;i++) tmp[i] = dis[i];

	int ans = 0;
	for(i=1;i<=n;i++)
	{
		int x = SPFA(i,src);
		if(x+tmp[i]>ans) ans = x+tmp[i];
	}
	printf("%d\n",ans);
	return 0;
}