算法1

朴素dijkstra，O（n2）

正向建图，反向建图，两次dijkstra

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1010, M = 100010;
int n, m, x;
vector<vector<int>> gc(1010, vector<int>(1010, 0x3f3f3f3f));
vector<vector<int>> go(1010, vector<int>(1010, 0x3f3f3f3f));
int distcome[N];
int distgo[N];
int st[N];

void dijkstra(int dist[], vector<vector<int> >& g)
{
    memset(st, 0, sizeof st);
    dist[x] = 0;
    for(int i = 1; i <= n; ++ i)
    {
        int t = -1;
        for(int j = 1; j <= n; ++ j)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        st[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;
    int a, b, c;
    for(int i = 1; i <= m; ++ i)
    {
        cin >> a >> b >> c;
        gc[a][b] = min(gc[a][b], c);
        go[b][a] = min(go[b][a], c);
    }
    memset(distcome, 0x3f, sizeof distcome);
    dijkstra(distcome, gc);
    memset(distgo, 0x3f, sizeof distgo);
    dijkstra(distgo, go);
    int res = 0;
    for(int i = 1; i <= n; ++ i)
        if(i != x)
            res = max(res, distcome[i] + distgo[i]);
    cout << res;
    return 0;
}