#include <iostream>
using namespace std;
int G[1008][1008];
int D[1008];
void dijkstra(int v0,int n)
{
	int i;
	short int *flag=new short int [n];
	for(i=0;i<n;i++)
	{
		D[i]=G[v0][i];
		flag[i]=0;
	}
	D[v0]=0;flag[v0]=1;
	int tempn=n-1;
	while(tempn--)//循环n-1次
	{
		int Dpos;
		int min=1000;
		for(i=0;i<n;i++)
		{
			if(flag[i]==0)
				if(D[i]<min)
				{
					min=D[i];
					Dpos=i;
				}
		}
		flag[Dpos]=1;
		for(i=0;i<n;i++)
			if(flag[i]==0)
				if((D[Dpos]+G[Dpos][i])<D[i])
				{
					D[i]=(D[Dpos]+G[Dpos][i]);
				}
	}
	delete [] flag;
}
void rev(int n)
{
	int i,j;
	int temp;
	for(i=0;i<(n-1);i++)
		for(j=i+1;j<n;j++)
		{
			temp=G[i][j];
			G[i][j]=G[j][i];
			G[j][i]=temp;
		}
}
void out(int n);
void outt(int n,int *distt);
int main()
{
	int i,j;
	for(i=0;i<1008;i++)
		for(j=0;j<1008;j++)
			if(i==j)G[i][j]=0;
			else G[i][j]=1000;

	int n,m,x;
	cin>>n>>m>>x;
	while(m--)
	{
		int s,d,we;
		cin>>s>>d>>we;
		G[s-1][d-1]=we;
	}
//	out(n);
	dijkstra(x-1,n);
//	outt(n,D);
	int *d1=new int [n];
	for(i=0;i<n;i++)d1[i]=D[i];
	rev(n);
//	out(n);
	dijkstra(x-1,n);
//	outt(n,D);
  	int max=0;
	for(i=0;i<n;i++)
		if(i!=(x-1))
			if(D[i]!=1000&&d1[i]!=1000)
				if((d1[i]+D[i])>max)max=(d1[i]+D[i]);
	cout<<max<<endl;
    return 0;	
}
void out(int n)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			if(i==j)cout<<0<<"   ";
			else if(G[i][j]==1000)cout<<"~  ";
				else cout<<G[i][j]<<"   ";
		cout<<endl<<endl;
	}
}
void outt(int n,int *distt)
{
	int i;
	for(i=0;i<n;i++)
		if(distt[i]==1000)cout<<"~  ";
		else	cout<<distt[i]<<"  ";
	cout<<endl;
}
	

	

• Re:WA了25次了 新突破!!! (6) zhouqian 2008-12-14 14:51:20