题目描述

寒假到了，n 头牛都要去参加一场在编号为 x 的牛的农场举行的派对，农场之间有 m 条有向路，每条路都有一定的长度。

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

输入格式

第一行有三个整数，分别表示牛的数量 n，道路数 m 和派对农场编号 x。
接下来 m 行，每行三个整数 u, v, w 表示存在一条由 u 通向 v 的长度为 w 的道路。

输出格式

输出一行一个整数表示答案。

输入

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

输出

10

题解

单源最短路&单终点最短路
单终点最短路径其实就可以把所有的边反过来，直接就转换为单源最短路径了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,double> PID;
const int INF=0x3f3f3f3f;
const LL LNF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=1010;
int g[N][N];
int rg[N][N];
int dist[N];
int rdist[N];
bool vis[N];
int n,m,x;

void dijkstra(int g[][N],int dist[])
{
    memset(dist,0x3f,sizeof rdist);//不能用函数里面的d进行sizeof, 因为那是指针
    memset(vis,0,sizeof vis);
    dist[x]=0;

    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!vis[j] && (t==-1 || dist[t] > dist[j])) t=j;
        vis[t]=true;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
}

int main()
{
    cin>>n>>m>>x;

    memset(g,0x3f,sizeof g);
    memset(rg,0x3f,sizeof rg);

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=c;
        rg[b][a]=c;
    }

    dijkstra(g,dist);
    dijkstra(rg,rdist);

    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,dist[i]+rdist[i]);

    cout<<ans<<endl;
    // system("pause");
}