先算源点x的最短路 然后取反图再算一遍最短路 求两次的和最大值

#include<stdio.h>
#include<string.h>
#include<stdbool.h>

#define N 1010
#define INF 0x3f3f3f3f

int n, m, x;
int g[N][N];
int dist[N];
int dist2[N];
bool st[N];

int min(int a, int b){  return a < b ? a : b;  }

void dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, 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[t] > dist[j]))
                t = j;

        st[t] = true;

        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
}

int main(){

    scanf("%d %d %d", &n, &m, &x);
    memset(g, 0x3f, sizeof g);

    while(m--){
        int a, b, t;
        scanf("%d %d %d", &a, &b, &t);
        g[a][b] = min(g[a][b], t);
    }

    dijkstra();
    memcpy(dist2, dist, sizeof dist);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++){
            int temp = g[i][j];
            g[i][j] = g[j][i];
            g[j][i] = temp;
        }

    dijkstra();

    int max = -INF;
    for(int i = 1; i <= n; i++)
        if(dist[i] + dist2[i] > max)
            max = dist[i] + dist2[i];

    printf("%d", max);

    return 0;
}