#include<iostream>
#include<memory>
using namespace std;
const int int_max=INT_MAX/2;
bool found[1002];
int dist[2][1002];
int cost[2][1002][1002];
void shortestpath(int x,int n,int g)
{
	int i,j,min;
	for(i=1;i<=n;i++)
	{
		found[i]=false;
		dist[g][i]=int_max;
	}
	dist[g][x]=0;
	while(x!=-1)
	{
       found[x]=true;
	   for(i=1;i<=n;i++)
	   {
		   if((!found[i])&&cost[g][x][i])
			   if(dist[g][i]>dist[g][x]+cost[g][x][i])
                    dist[g][i]=dist[g][x]+cost[g][x][i];
	   } 
	   min=int_max;
       x=-1;
	   for(j=1;j<=n;j++)
		   if((!found[j])&&dist[g][j]<min)
		   {
			   min=dist[g][j];
			   x=j;
		   }
	}
}
int main()
{
  int n,m,x;
    while(scanf("%d%d%d",&n,&m,&x)!=EOF)
  {
	  int i,x,y,d,min=0;
      memset(cost,0,sizeof(cost));
	  for(i=1;i<=m;i++)
	  {
		  scanf("%d%d%d",&x,&y,&d);
		  cost[0][x][y]=d;
		  cost[1][y][x]=d;
	  }
      shortestpath(x,n,0);
      shortestpath(x,n,1);
	 for(i=1;i<=n;i++)
	 {
		 if(dist[0][i]+dist[1][i]>min)
			 min=dist[0][i]+dist[1][i];
	 }
	 printf("%d\n",min);
  }
    return 0;
}

• Re:为什么wa？ (1231) 200892458 2009-05-19 21:15:46