题目链接：http://poj.org/problem?id=3268
题目大意：有编号为1－N的牛，它们之间存在一些单向的路径。给定一头牛的编号，其他牛要去拜访它并且拜访完之后要返回自己原来的位置，求这些牛中所花的最长的来回时间是多少。

每头牛返回的最短时间从目标牛为起点求单源最短路径。但每头牛出发到目标牛的最短时间无法直接算出来，稍微转换一下，发现这个最短时间其实可以通过把所有的边取反向(矩阵转置) 。然后再从目标牛求一次单源最短路径得到。得到这两个最短路径之后，取它们的和的最大者即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
const int maxn=1005;

vector< pair<int ,int > > e[maxn];
int n, m, x;
int d1[maxn], vis[maxn];   //dis当前的最短路 vis是否在队列中
int d2[maxn];

struct E
{
    int x, y, z;
}node[100005];

queue<int> q;
void spfa(int s, int t, int dis[])
{
    while(!q.empty())
    {
        q.pop();
    }
    q.push(s);
    dis[s]=0, vis[s]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop(), vis[now]=0;
        for(int i=0;i<e[now].size();i++)//访问所有的邻接点
        {
            int v=e[now][i].first;
            if(dis[v]>dis[now]+e[now][i].second)
            {
                dis[v]=dis[now]+e[now][i].second;
                if(vis[v]==1)
                {
                    continue;
                }
                q.push(v);             //把所有不在队列的邻接点加入队列
                vis[v]=1;
            }
        }
    }

}

int main()
{
    while(scanf("%d%d%d",&n,&m,&x)!=EOF)
    {
        for(int i=0;i<maxn;i++)  //初始化
        {
            d1[i]=1e9;
            d2[i]=1e9;
            vis[i]=0;
            e[i].clear();
        }

        for(int i=0;i<m;i++)
        {
            int x, y, z;
            scanf("%d%d%d",&x,&y,&z);
            node[i].x=x, node[i].y=y, node[i].z=z;
            e[x].push_back(make_pair(y ,z));
        }
        spfa(x, n, d1);

        for(int i=0;i<maxn;i++)//取反再跑spfa
        {
            vis[i]=0;
            e[i].clear();
        }
        for(int i=0;i<m;i++)
        {
            int x=node[i].x, y=node[i].y, z=node[i].z;
            e[y].push_back(make_pair(x ,z));
        }
        spfa(x, n, d2);

        int ans=0;
        for(int i=1;i<=n;i++)
        {
            ans=max(ans, d1[i]+d2[i]);
        }
        printf("%d\n",ans);
    }

    return 0;
}