题意：一些牛要去某一点參加聚会，然后再回到自己家，路是单向的，问花费时间最多的那头牛最少须要花费多长时间。

思路：从聚会地点返回，相当于是从某一点到其它各个点的最短路径。从牛的家中走到聚会地点，能够把路径反过来变成从聚会地点到各个点的最短路径，两个最短路径值加起来就是每头牛所花费的最小时间，找出最大的就可以。

我用了两个邻接表存路径，事实上这道题用邻接矩阵存更好做，矩阵横纵坐标翻转就把路径反转了，我用SPFA写想练练手，一直都不会手写SPFA，做几道题找找感觉。

AC竟然用时0MS。。

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 100100

#define eps 1e-7

#define INF 0x7FFFFFFF

#define seed 131

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

struct node{

    int u,v,next;

}edge[MAXN],redge[MAXN];

int head[MAXN],rhead[MAXN],dist[MAXN],vis[MAXN],ans[MAXN];

int cnt,rcnt,n,m,x;

void add_edge(int a,int b,int c){

    edge[cnt].u = b;

    edge[cnt].v = c;

    edge[cnt].next = head[a];

    head[a] = cnt++;

    redge[rcnt].u = a;

    redge[rcnt].v = c;

    redge[rcnt].next = rhead[b];

    rhead[b] = rcnt++;

}

void spfa(int type){

    int i,j;

    for(i=1;i<=n;i++){

        dist[i] = INF;

    }

    dist[x] = 0;

    memset(vis,0,sizeof(vis));

    vis[x] = 1;

    queue<int>q;

    q.push(x);

    while(!q.empty()){

        int temp = q.front();

        q.pop();

        vis[temp] = 0;

        for(i=type?rhead[temp]:head[temp];i!=-1;i=type?redge[i].next:edge[i].next){

            int lu = type?redge[i].v:edge[i].v;

            if(lu+dist[temp]<dist[type?redge[i].u:edge[i].u]){

                dist[type?redge[i].u:edge[i].u] = lu + dist[temp];

                if(!vis[type?redge[i].u:edge[i].u]){

                    vis[type?redge[i].u:edge[i].u] = 1;

                    q.push(type?redge[i].u:edge[i].u);

                }

            }

        }

    }

}

int main(){

    int i,j,a,b,c;

    scanf("%d%d%d",&n,&m,&x);

    memset(head,-1,sizeof(head));

    memset(rhead,-1,sizeof(rhead));

    cnt = rcnt = 0;

    int maxm = 0;

    for(i=0;i<m;i++){

        scanf("%d%d%d",&a,&b,&c);

        add_edge(a,b,c);

    }

    spfa(0);

    for(i=1;i<=n;i++){

        if(i!=x)    ans[i] = dist[i];

    }

    spfa(1);

    for(i=1;i<=n;i++){

        if(i!=x)    ans[i] += dist[i];

        if(ans[i]>maxm) maxm = ans[i];

    }

    printf("%d\n",maxm);

    return 0;

}