Time Limit: 1 second

Memory Limit: 256 MB

【问题描述】

N头牛要去参加一场在编号为X（1≤X≤n）的牛的农场举行的派对（1≤N≤1000），有M（1≤M≤100000）条有向道路，每条路长ti（1≤ti≤100）；

每头牛都必须参加完派对后回到家，每头牛都会选择最短路径，求这N头牛的最短路径（一个来回）中最长的一条的长度。

特别提醒：可能有权值不同的重边。

【输入格式】

第一行：N，M，X；

第二~M+1行：Ai，Bi，Ti，表示有一条从Ai到Bi的路，长度为Ti

【输出格式】

最长最短路的长度。

【输入样例1】

4 8 2

1 2 4

1 3 2

1 4 7

2 1 1

2 3 5

3 1 2

3 4 4

4 2 3

【输出样例1】

10

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t018

【题意】



中文题

【题解】



在反图和正图上各自跑一遍spfa;

求出x点到其他点的最短路;

正图和反图加起来就是这个人到x再回家的最短路了;

枚举取最大值就好;



【完整代码】

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

#define lson l,m,rt<<1

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

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%I64d",&x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int M = 109000;

const int N = 1100;

struct abc

{

    int en,w,nex;

};

int n,m,x,tot[2]={0},dis[2][N],fir[2][N];

abc g[2][M];

queue <int> dl;

bool exsit[N];

void add(int p,int x,int y,int z)

{

    g[p][++tot[p]].nex = fir[p][x];

    fir[p][x] = tot[p];

    g[p][tot[p]].en = y,g[p][tot[p]].w = z;

}

void spfa(int p)

{

    memset(dis[p],0x3f3f3f3f,sizeof dis[p]);

    memset(exsit,false,sizeof exsit);

    dis[p][x] = 0;

    dl.push(x),exsit[x] = true;

    while (!dl.empty())

    {

        int xx = dl.front();

        dl.pop(),exsit[xx] = false;

        for (int i = fir[p][xx];i;i = g[p][i].nex)

        {

            int y = g[p][i].en;

            if (dis[p][y]>dis[p][xx]+g[p][i].w)

            {

                dis[p][y] = dis[p][xx] + g[p][i].w;

                if (!exsit[y])

                {

                    exsit[y] = true;

                    dl.push(y);

                }

            }

        }

    }

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    rei(n);rei(m);rei(x);

    rep1(i,1,m)

    {

        int x,y,z;

        rei(x);rei(y);rei(z);

        add(0,x,y,z),add(1,y,x,z);

    }

    spfa(0),spfa(1);

    int ma = dis[0][1]+dis[1][1];

    rep1(i,2,n)

        if (ma<dis[0][i]+dis[1][i])

            ma = dis[0][i]+dis[1][i];

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

    return 0;

}