思路与算法

把每头牛的往返路拆成到X和从X返回两部分。原图从X出发求返回距离，所有道路反向后从X出发求原图到X的距离。两次使用堆优化Dijkstra，最后最大化两距离之和。保留重边，让松弛自行选择较优费用。

正确性说明

反向图中X到u的道路与原图u到X的道路逐边一一对应且总权相同。正权下Dijkstra每次取出的最小未定距离不会再改善；两段旅程独立选择最短路，故其和就是各牛最短往返距离，取最大即答案。

复杂度

建两图O(N+M)，两次Dijkstra O((N+M)log(N+M))时间，距离初始化O(N)，总空间O(N+M)。

易错点

道路有方向；重边不能随意去重为较大权。输入情境要求参加后回家，本数据均保证往返可达，X本身贡献0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
vector<int> dij(int s, const vector<vector<pair<int, int>>> &g) {
    vector<int> d(g.size(), 1000000000);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    d[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        if (t.first != d[t.second])
            continue;
        for (auto e : g[t.second])
            if (d[e.first] > t.first + e.second) {
                d[e.first] = t.first + e.second;
                q.push({d[e.first], e.first});
            }
    }
    return d;
}
int main() {
    int n, m, x;
    cin >> n >> m >> x;
    --x;
    vector<vector<pair<int, int>>> g(n), h(n);
    while (m--) {
        int a, b, w;
        cin >> a >> b >> w;
        --a;
        --b;
        g[a].push_back({b, w});
        h[b].push_back({a, w});
    }
    auto a = dij(x, g), b = dij(x, h);
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, a[i] + b[i]);
    cout << ans << '\n';
}