https://vjudge.net/problem/POJ-3268
题目大意：
n个农场的n头奶牛将前往x农场，要选择一条来回时间最短的路径。
（一头牛的返回路线可能不同于她最初去派对的路线，因为道路是单向的。）
思路：
//有向图的迪杰斯特拉
如果以每头牛为起点遍历其到x的最短路，耗时太大。
有没有简便的方法呢？
如果，以x为起点，找到其余点的最短路，这求出的便是牛返回各自农场的最短路，
由于还要求牛前往x农场的最短路，
我们可以想到一个巧妙的方法：将所有的方向反向，再求一遍以x为起点，找到其余点的最短路。
所以就是在最短路的代码上加一个反向最短路。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define maxn 1005
#define inf 0x3f3f3f3f
using namespace std;
int cost[maxn][maxn],n,m,x;
int disback[maxn],discome[maxn];
bool vis[maxn];
int dij(int x)
{
int u,minn;
for(int i=;i<=n;i++)
{
disback[i]=cost[x][i];
discome[i]=cost[i][x];//将各边反转
}
for(int i=;i<n;i++)
{
u=-,minn=inf;
for(int j=;j<=n;j++)
{
if(!vis[j]&&disback[j]<minn)
{
u=j;
minn=disback[j];
}
}
//if(u=-1)return
vis[u]=;
for(int v=;v<=n;v++)
{
if(!vis[v]&&cost[u][v]!=inf)
{
if(disback[u]+cost[u][v]<disback[v])
disback[v]=disback[u]+cost[u][v];
}
}
}
memset(vis,,sizeof vis);
for(int i=;i<n;i++)
{
minn=inf,u=-;
for(int j=;j<=n;j++)
{
if(!vis[j]&&discome[j]<minn)
{
u=j;
minn=discome[j];
}
}
vis[u]=;
for(int j=;j<=n;j++)
{
if(!vis[j]&&cost[j][u]+discome[u]<discome[j])
discome[j]=cost[j][u]+discome[u];
}
}
minn=-;
for(int i=;i<=n;i++)
minn=max(minn,discome[i]+disback[i]);
return minn;
}
int main()
{
int i,a,b,c,j;
while(~scanf("%d%d%d",&n,&m,&x))
{
for(i=;i<=n;i++)
for(j=;j<=n;j++)
{
if(i!=j)
cost[i][j]=inf;
else
cost[i][j]=;
}
for(i=;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
cost[a][b]=c;
}
printf("%d\n",dij(x));
}
return ;
}