农场派对

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1550 字
正反两图各跑一次Dijkstra来回求和
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1497
// 题意：有向图，N 头牛都要去 X 号农场再返回，各自走最短路，求所有牛来回总路程中的最大值。
// 思路：在反图上从 X 跑 Dijkstra 得到 X 到各点的距离，在原图上从 X 跑 Dijkstra 得到各点到 X 的距离，两者相加取最大。
// 复杂度：O(M log N) 时间 / O(N+M) 空间
// 易错点：可能有权值不同的重边，邻接表要全部存下来不能去重；来回两段要分别在原图和反图上求，方向别搞反。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
struct Edge{
    int to, w;
};
vector<Edge> g[MAXN];
vector<Edge> rg[MAXN];
int distA[MAXN];
int distB[MAXN];
void dijkstra(vector<Edge> adj[], int src, int dista[], int n){
    for(int i = 1; i <= n; i++) dista[i] = INF;
    dista[src] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});
    while(!pq.empty()){
        int du = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(du != dista[u]) continue;
        for(size_t i = 0; i < adj[u].size(); i++){
            int v = adj[u][i].to;
            int w = adj[u][i].w;
            if(du + w < dista[v]){
                dista[v] = du + w;
                pq.push({dista[v], v});
            }
        }
    }
}
int main(){
    int n, m, x;
    if(!(cin >> n >> m >> x)) return 0;
    for(int i = 0; i < m; i++){
        int a, b, t;
        cin >> a >> b >> t;
        g[a].push_back({b, t});
        rg[b].push_back({a, t});
    }
    dijkstra(rg, x, distA, n);
    dijkstra(g, x, distB, n);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(distA[i] + distB[i] > ans) ans = distA[i] + distB[i];
    }
    cout << ans << '\n';
    return 0;
}
农场派对

正文

一本通·提高篇的其它内容
