本文共 2864 字，大约阅读时间需要 9 分钟。

题意

单向图，N - 1个牛去聚会，求所有牛去聚会和回家路径和的最大值

AC

• 很骚的操作
  首先从派对的地方跑Dijkstra求出回家的最短路，然后将所有边翻转再次从聚会跑Dijkstra就是所有牛到聚会的最短路
  一共跑 2 个Dijkstra

using namespace std;int inf = 0x3f3f3f3f;int g[N][N];int temp[N], dis[N];bool vis[N];bool vis_c[N][N];void Dijkstra(int start, int n) {    mem(dis, inf);    mem(vis, false);    dis[start] = 0;    for (int i = 1; i <= n; ++i) {        int MIN = inf, u = -1;        for (int j = 1; j <= n; ++j) {            if (vis[j]) continue;            if (dis[j] < MIN) {                MIN = dis[j];                u = j;            }        }        if (u == -1)    return;        vis[u] = true;        for (int j = 1; j <= n; ++j) {            if (g[u][j] == inf || vis[j]) continue;            if (dis[j] > dis[u] + g[u][j]) {                dis[j] = dis[u] + g[u][j];            }        }    }}int main(){//  freopen("in.txt", "r", stdin);    int n, m, x;    cin >> n >> m >> x;    mem(g, inf);    for (int i = 0; i < m; ++i) {        int u, v, c;        cin >> u >> v >> c;        g[u][v] = min(g[u][v], c);    }    // 牛回家的最短路    Dijkstra(x, n);    for (int i = 1; i <= n; ++i) {        temp[i] = dis[i];    }    // 翻转边    mem(vis_c, false);    for (int i = 1; i <= n; ++i) {        for (int j = 1; j <= n; ++j) {            if (g[i][j] != inf && vis_c[i][j] == false) {                swap(g[i][j], g[j][i]);                vis_c[j][i] = vis_c[i][j] = true;            }        }    }    // 牛去派对的最短    Dijkstra(x, n);    int ans = 0;    for (int i = 1; i <= n; ++i) {        temp[i] += dis[i];        ans = max(ans, temp[i]);    }    cout << ans << endl;    return 0;}

• 堆优化Dijkstra
  一共跑N + 1 个Dijkstra

using namespace std;int inf = 0x3f3f3f3f;struct ac{    int v, c;};vector
   
     g[N];int dis[N], temp[N];bool vis[N];void Dijkstra(int start, int n) {    mem(dis, inf);    mem(vis, false);    dis[start] = 0;    priority_queue
    
     , greater
     
 > que;    que.push(P(0, start));    while (!que.empty()) {        P f = que.top();        int v = f.second;        int c = f.first;        que.pop();        if (dis[v] < c || vis[v])    continue;        vis[v] = true;        for (int j = 0; j < g[v].size(); ++j) {            ac t = g[v][j];            if (vis[t.v])   continue;            if (dis[t.v] > c + t.c) {                dis[t.v] = c + t.c;                que.push(P(dis[t.v], t.v));            }        }    }}int main(){    // freopen("in.txt", "r", stdin);    int n, m, x;    cin >> n >> m >> x;    for (int i = 0; i < m; ++i) {        int u, v, c;        cin >> u >> v >> c;        g[u].push_back((ac){v, c});    }    // 牛回家的最短路    Dijkstra(x, n);    for (int i = 1; i <= n; ++i) {        temp[i] = dis[i];    }    int ans = 0;    // 每个牛去聚会的最短路    for (int i = 1; i <= n; ++i) {        if (i == x) continue;        Dijkstra(i, n);        temp[i] += dis[x];        ans = max(temp[i], ans);    }    cout << ans << endl;    return 0;}
    
   

转载地址：http://skprf.baihongyu.com/