D - Silver Cow Party POJ - 3268——————最短路+思维（两遍单元最短路）-蒲公英云

D - Silver Cow Party POJ - 3268——————最短路+思维（两遍单元最短路）

题目连接

https://vjudge.net/contest/313997#problem/D

大体思路：

这个题用floyd 会T的
所以就要 顺这跑一边最短路， 逆着跑一边最短路

详细思路+代码

/****** 题目要求： 是 询问 最快来回一趟， 耗时最大的那头牛所用的时间 两边单源最短路就行 ①首先可以求出 从聚会点返回到牛棚的最短路径【这个你们都会】 ②从牛棚去的时候的最短路径就是： 可以看成 从聚会点沿着路 反向的最短路( u到v 的最短路 可以看成 v到u的 沿着路反向走的最短路径) *******/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int maxn = 1e3+50;
const ll inf = 0x3f3f3f3f;
ll mp[maxn][maxn];
ll mp2[maxn][maxn];// 存反向图
int N, M, X;
void init()
{ 
    for(int i = 1;i <= N;i++)
    { 
        for(int j = 1;j <= N;j++)
        { 
            mp[i][j] = inf;
            mp2[i][j] = inf;
        }
    }
    for(int i = 1;i <= N;i++)
    { 
        mp[i][i] = 0;
        mp2[i][i] = 0;
    }
}
void floyd()
{ 
    for(int k = 1;k <= N;k++)
        for(int i = 1;i <= N;i++)
            for(int j = 1;j <= N;j++)
                 if(mp[i][k]!= inf &&mp[j][k]!=inf&&mp[i][k]+mp[k][j] < mp[i][j])
                    mp[i][j] = mp[i][k]+mp[k][j];
}
void spfa(int s, ll mpx[][maxn])
{ 
    queue<int>q;//
    while(!q.empty())q.pop();//
    bool vis[maxn];//
    for(int i = 1;i <= N;i++)vis[i] = false;//
    ll dis[maxn];
    for(int i = 1;i <= N;i++)dis[i] = inf;//
    dis[s] = 0;//
    q.push(s);
    vis[s] = true;
    while(!q.empty())
    { 
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = 1;i <= N;i++)
        { 
            if(dis[i] > dis[u]+mpx[u][i])
            { 
                dis[i] = dis[u]+mpx[u][i];
                if(!vis[i])
                { 
                    q.push(i);
                    vis[i] = true;
                }
            }
        }
    }
    for(int i = 1;i <= N;i++)
    { 
        mpx[s][i] = dis[i];
    }
}
int main()
{ 
    scanf("%lld %lld %lld", &N, &M, &X);
    init();
    while(M--)
    { 
        ll u, v, w;
        scanf("%lld %lld %lld", &u, &v, &w);
        if(w < mp[u][v])mp[u][v] = w;// 图
        if(w < mp2[v][u])mp2[v][u] = w;// 反向图
    }
    spfa(X, mp);
    spfa(X, mp2);
    ll ans = 0;
    for(int i = 1;i <= N;i++)
    { 
        ans = max(ans, mp[X][i]+mp2[X][i]);
    }
    printf("%lld", ans);
    return 0;
}