题意：

n个地方，标号1~n，每个地方都有一头牛，现在要他们都去往标号为x的地方，再从x返回，每条道路都是单向的，求所有牛走的来回的最短路中的最大值。

分析：

注意在求每头牛走到x时，挨个算肯定超时，可以在将道路反向处理，都变成从x出。之前用vector模拟邻接表超时，后来用链表和数组分别模拟了邻接表，好像数组模拟的更快一些。

代码:

链表：

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int maxn =1005, maxm = 100005, INF = 0x3fffffff;

struct edge

{

   int to, w;

   edge* next;

};

int n, m, x;

int in[maxn], d[maxn], d1[maxn];

edge* head[maxn];

edge* head2[maxn];

queue<int>q;

void spfa()

{

    fill(d, d+1+n,INF);

    fill(in, in + 1 + n, 0);

    d[x] = 0;

    q.push(x);

    in[x] = 1;

    while(!q.empty()){

        int a = q.front();

        edge* t =head[a];q.pop();

        in[a] = 0;

        while(t!=NULL){

            if(d[t->to]>d[a]+t->w){

                d[t->to] = d[a] + t->w;

                if(!in[t->to]){q.push(t->to);in[t->to] = 1;}

            }

            t = t->next;

        }

    }

    return;

}

void spfa2()

{

    fill(d1, d1+1+n,INF);

    fill(in, in + 1 + n, 0);

    d1[x] = 0;

    q.push(x);

    in[x] = 1;

    while(!q.empty()){

        int a = q.front();

        edge* t=head2[a];q.pop();

        in[a] = 0;

        while(t!=NULL){

            if(d1[t->to]>d1[a]+t->w){

                d1[t->to] = d1[a] + t->w;

                if(!in[t->to]){q.push(t->to);in[t->to] = 1;}

            }

            t = t->next;

        }

    }

    return;

}

int main (void)

{

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

        int t1, t2, t3;

        int res = 0;

        memset(head, 0,sizeof(head));

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

            scanf("%d%d%d", &t1, &t2, &t3);

            edge* temp=new edge;

            edge* temp2 = new edge;

            temp->to = t2;

            temp->w= t3;

            temp->next = NULL;

            if(head[t1]==NULL) head[t1] = temp;

            else {

                temp->next =head[t1];

                head[t1] = temp;

            }

            temp2->to = t1;

            temp2->w = t3;

            temp2->next = NULL;

            if(head2[t2]==NULL) head2[t2] = temp2;

            else {

                    temp2->next = head2[t2];

                    head2[t2] = temp2;

            }

        }

       spfa();

       spfa2();

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

        if(i!=x&&res<d[i]+d1[i]) res = d[i]+d1[i];

       }

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

  }

数组：

#include<cstdio>

#include<iostream>

#include<queue>

using namespace std;

int n, m, x;

struct edge{

    int to,w;

    int next;

};

const int maxn =1005, maxm = 100005, INF = 0x3fffffff;

int head[maxn], head2[maxn];

edge e[maxm], re[maxm];

int in[maxn], d[maxn], d1[maxn];

void spfa()

{

    fill(d, d+n+1,INF);

    fill(in, in+n+1,0);

    queue<int>q;

    q.push(x);

    in[x] = 1;

    d[x] = 0;

    while(!q.empty()){

        int tmp = q.front();q.pop();

        in[tmp] = 0;

        int t = head[tmp];

        while(t!=-1){

            if(d[e[t].to] > d[tmp] + e[t].w){

                d[e[t].to] = d[tmp] + e[t].w;

                if(!in[e[t].to]){

                        q.push(e[t].to);

                        in[e[t].to] = 1;

            }

        }

         t = e[t].next;

    }

    }

}

void spfa2()

{

    fill(d1,d1+n+1,INF);

    fill(in, in+n+1,0);

    queue<int>q;

    q.push(x);

    in[x] = 1;

    d1[x] = 0;

    while(!q.empty()){

        int tmp = q.front();q.pop();

        in[tmp] = 0;

        int t = head2[tmp];

        while(t!=-1){

            if(d1[re[t].to] > d1[tmp]+re[t].w){

                d1[re[t].to] = d1[tmp] + re[t].w;

                if(!in[re[t].to]){

                        q.push(re[t].to);

                        in[re[t].to] = 1;

            }

        }

        t = re[t].next;

    }

    }

}

int main (void)

{

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

    int a, b ,c;

    fill(head, head+n+1, -1);

    fill(head2, head2+n+1, -1);

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

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

            e[i].to = b, e[i].w = c;

            e[i].next = head[a];

            head[a] = i;

            re[i].to = a, re[i].w =c;

            re[i].next = head2[b];

            head2[b] = i;

    }

    spfa();

    spfa2();

    int res = 0;

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

        if(i!=x&&res<d[i]+d1[i]) res = d[i]+d1[i];

    }

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

}