Silver Cow Party

水题

反向建边，再跑一遍dij就可以了
##代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<functional>
#include<cstdio>
using namespace std;
typedef pair<int, int> pii;
const int max_n = 1200;
const int inf = 2e9;
const int max_m = 1e5 + 100;
struct edge{
    int to, cost, next;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cost) {
    E[cnt].to = to;E[cnt].cost = cost;
    E[cnt].next = head[from];head[from] = cnt++;
}

int d[max_n];
void dijstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii> > que;
    fill(d, d + max_n, inf);
    d[s] = 0;que.push(make_pair(d[s], s));
    while (!que.empty()) {
        pii p = que.top();que.pop();
        int u = p.second;int dist = p.first;
        if (dist > d[u])continue;
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (d[e.to] > d[u] + e.cost) {
                d[e.to] = d[u] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

int n, m, x;
int us[max_m], vs[max_m], c[max_m];
int d1[max_n];
int main() {
    scanf("%d %d %d", &n, &m, &x);
    for (int i = 1;i <= m;++i)
        scanf("%d %d %d", &us[i], &vs[i], &c[i]);
    for (int i = 1;i <= m;++i)
        add(us[i], vs[i], c[i]);
    dijstra(x);
    for (int i = 1;i <= n;++i)d1[i] = d[i];
    fill(head, head + max_n, 0);cnt = 1;
    for (int i = 1;i <= m;++i)
        add(vs[i], us[i], c[i]);
    dijstra(x);
    int ans = 0;
    for (int i = 1;i <= n;++i)
        ans = max(ans, d[i] + d1[i]);
    printf("%d", ans);
}