poj 3268 Silver Cow Party

Silver Cow Party

题目链接：http://poj.org/PRoblem?id=3268

题目大意：在所有的牛场中选一个，其他牛场的牛都会走个来会，路径是单向的，在所有的来回中求个最大的。数据是1000，如果用弗洛伊德O（n^3）h会超时；

所以这里用迪杰斯特拉，但是还必须用一个小技巧，题目要求都与X农场有关，到X和从X出发。所以可以在函数里动手脚，也可以在map里面做文章。

代码如下：

#include<iostream>  #include<cstdio>  #include<cstring>  using namespace std;  #define INF 0x3f3f3f3; int map[1005][1005],dis[1005],visited[1005];  int xx[1005],nn[1005];int map2[1005][1005];void Dj(int n,int x)  {      int p;      for(int i=1;i<=n;i++)      {          dis[i]=map[x][i];          visited[i]=0;    }    visited[x]=1;    for(int i=1;i<=n;i++)      {          int min=INF;        for(int j=1;j<=n;j++)        {              if(!visited[j] && dis[j]<min)                   {                  p=j;                  min=dis[j];              }          }          visited[p]=1;             for(int j=1;j<=n;j++)          {              if(!visited[j] && dis[p]+map[p][j]<dis[j])                  {                      dis[j]=dis[p]+map[p][j];            }          }      }  }    int main()  {      int n,m,r;    int x,y,d;    while(~scanf("%d%d%d",&n,&m,&r))    {          for(int i=1;i<=n;i++)             for(int j=1;j<=n;j++)                 map[i][j]=map2[i][j]=INF;         for(int i=1;i<=m;i++)         {              scanf("%d%d%d",&x,&y,&d);              map[x][y]=d;            map2[y][x]=d;        }               	Dj(n,r);       	for(int j=1;j<=n;j++)        {       		xx[j]=dis[j];		}		for(int i=1;i<=n;i++)             for(int j=1;j<=n;j++)                 map[i][j]=map2[i][j];		Dj(n,r);       	for(int j=1;j<=n;j++)        {       		nn[j]=dis[j];		}		int MAX=-1;		for(int i=1;i<=n;i++)		{			if(i!=r)			{				if(nn[i]+xx[i]>MAX)					MAX=nn[i]+xx[i];			}		}        printf("%d/n",MAX);    }    return 0;  }