题目描述

最长距离
有 n 个人，分别在编号1 - n的城市，现在去城市 x 聚会，图有 m 条有向路径组成，每一个人到达城市 x 之后，
仍然需要返回初始城市。每一个人的时间消耗为往返距离之和，已知每个人都会走最短的路径，求消耗时间最长
的一个人消耗的时间是多少？(1 <= n <= 1e3,1 <= m <= 1e6,1 <= l <= 1e4)

朴素版dijkstra

$O(n^2)$

初看题目去程是求每一个节点到城市 x 最短路径，回城是以 x 为起点的有源最短路径。细想一下去程的问题可以进行改装： 将所有路径反向，求以x为起点的有源最短路径，就是从其他点到达 x 的去程路径。
初始图求以 x 为起点的有源最短路径，将所有路径反向，再求以 x 为起点的有源最短路径，复杂度是朴素Dijkstra复杂度

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e3 + 10;
int g[N][N],dis[N],x,n,m,dis1[N],backup[N][N];
bool st[N];

int dijsk()
{
    memset(dis,0x3f,sizeof dis);
    dis[x] = 0;
    for (int i = 0;i < n;++i)
    {
        int t = -1;
        for (int j = 1;j <= n;++j)
            if (!st[j] && (-1 == t || dis[t] > dis[j])) t = j;
        st[t] = true;
        for (int j = 1;j <= n;++j)
            dis[j] = min(dis[j],dis[t] + g[t][j]);
    }
    memset(dis1,0x3f,sizeof dis1);
    memset(st,false,sizeof st);
    dis1[x] = 0;

    for (int i = 0;i < n;++i)
    {
        int t = -1;
        for (int j = 1;j <= n;++j)
            if (!st[j] && (-1 == t || dis1[t] > dis1[j])) t = j;
        st[t] = true;
        for (int j = 1;j <= n;++j)  dis1[j] = min(dis1[j],dis1[t] + g[j][t]);
    }
    int maxl = dis1[1] + dis[1];
    for (int i = 2;i <= n;++i)  maxl = max(maxl,dis[i] + dis1[i]);
    return maxl;
}

int main(void)
{
    cin>>n>>m;
    memset(g,0x7f,sizeof g);
    for (int i = 0;i < m;++i)
    {
        int a,b,c;
        scanf_s("%d%d%d",&a,&b,&c);
        g[a][b] = min(g[a][b],c);
    }
    cout<<dijsk()<<endl;
    return 0;
}