/*
**Author:zhangyehui
**Time:2011/4/13/16:15
*/
#include<iostream>
#include<cstring>
using namespace std;
#define MINT 0x7fffff
int N,M,X;
int map[1010][1010];
int dist1[1010];
int dist2[1010];
bool sign[1010];
void Dis1()
{
	int i,k;
	memset(sign,false,sizeof(sign));
	for(i=1;i<=N;i++)
		dist1[i]=map[X][i];
	sign[X]=true;
	dist1[X]=0;
	for(k=1;k<N;k++)
	{
		int min=MINT;
		int index=X;
		for(i=1;i<=N;i++)
		{
			if(sign[i]==false && dist1[i]<min)
			{
				min=dist1[i];
				index=i;
			}
		}
		sign[index]=true;
		dist1[index]=min;
		for(i=1;i<=N;i++)
		{
			if(sign[i]==false && dist1[i]>dist1[index]+map[index][i])
				dist1[i]=dist1[index]+map[index][i];
		}
	}

}

void Dis2()
{
	int i,k;
	memset(sign,false,sizeof(sign));
	for(i=1;i<=N;i++)
		dist2[i]=map[i][X];
	dist2[X]=0;
	sign[X]=true;
	for(k=1;k<N;k++)
	{
		int min=MINT;
		int index=X;
		for(i=1;i<=N;i++)
		{
			if(sign[i]==false && dist2[i]<min)
			{
				min=dist2[i];
				index=i;
			}
		}
		sign[index]=true;
		dist2[index]=min;
		for(i=1;i<=N;i++)
		{
			if(sign[i]==false && dist2[i]>dist2[index]+map[i][index])
				dist2[i]=dist2[index]+map[i][index];
		}
	}

}



int main()
{
	int i,j,a,b,c;
	cin>>N>>M>>X;
	for(i=1;i<=N;i++)
	{
		for(j=1;j<=N;j++)
			map[i][j]=MINT;
	}
	for(i=1;i<=M;i++)
	{
		cin>>a>>b>>c;
		if(c<map[a][b])
			map[a][b]=c;
	}

	Dis1();Dis2();
	/*for(i=1;i<=N;i++)
		cout<<dist1[i]<<" "<<dist2[i]<<endl;*/
	int max=dist1[1]+dist2[1];
	for(i=2;i<=N;i++)
		if(dist1[i]+dist2[i]>max) max=dist1[i]+dist2[i];
		cout<<max<<endl;
	return 0;
}

• 你把你赋的值输出看看就知道了。。。 (0) Stareven 2011-04-13 18:48:14
• Re:牛人请教一下，为什么最大值开到0xfffffff就错了，开到0x7fffff就对了 (14) Ruby931031 2012-03-21 09:44:55