#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <list>
#include <map>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <climits>
using namespace std;
const int N = 1005;
int n, m, x;
int mat[N][N], dist[N];


void dij(int s, int e) {
    bool vis[N];
    fill(vis + 1, vis + 1 + n, false);
    vis[s] = true;
    for (int i = 1; i < n; i++) {
        int Min = INT_MAX, p = -1;
        for (int j = 1; j <= n; j++) {
            if (mat[s][j] < Min && vis[j] == false) {
                Min = mat[s][j];
                p = j;
            }
        }
        if (p > 0) {
            vis[p] = true;
        }
        for (int i = 1; i <= n; i++) {
            if (vis[i] == false && mat[p][i] && dist[p] + mat[p][i] < dist[i]) {
                dist[i] = dist[p] + mat[p][i];
            }
        }
    }
}

void Init(int x) {
    fill(dist + 1, dist + 1 + n, INT_MAX);
    for (int j = 1; j <= n; j++) {
        if (mat[x][j]) {
            dist[j] = mat[x][j];
        }
    }
}

int main() {
    cin >> n >> m >> x;
    fill(mat + 1, mat + (n + 1) * (n + 1), INT_MAX);
    int a, b, v;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> v;
        mat[a][b] = v;
    }
    int Max = INT_MIN;
    for (int i = 1; i <= n; i++) {
        Init(i);
        dij(i, x);
        int m = dist[x];
        Init(x);
        dij(x, i);
        int n = dist[i];
        if (m + n > Max) {
            Max = m + n;
        }
    }
    cout << Max;
}

改了三个小时……

才拿10分（过了题中的样例输入）

我真的栓Q了啊