【t018】派对

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;
}