「SDOI 2009」Elaxia的路线

题目大意：求无向图中两对点间最短路的最长公共路径。$n \leq 1500$

第一想法是 $O(n^2\log n)$ 求出任意两点间的最短路后 $O(n^2)$ 暴力枚举公共路径。

正解考虑将二者最短路的交集上的所有边加入新图，那么新图一定是一个拓扑图，然后拓扑排序求最长链即可。

时间复杂度 $O(4n \log n)$

#include <cstdio>
#include <queue>
#include <cstring>

const int N = 1505, M = 2248505;
struct Edge {
    int v, w;
} e1[M], e2[M];
struct Pair {
    int x, y;
    bool operator < (const Pair &rhs) const {
        return x > rhs.x;
    }
};
std::queue<int> Q;
int head1[N], head2[N], nxt1[M], nxt2[M], dis[5][N], vis[N], dgr[N], s[5], tot1, tot2, n, m, ans;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void adde1(int u, int v, int w) {
    nxt1[++tot1] = head1[u];
    head1[u] = tot1;
    e1[tot1] = (Edge){v, w};
}
void adde2(int u, int v, int w) {
    nxt2[++tot2] = head2[u];
    head2[u] = tot2;
    e2[tot2] = (Edge){v, w};
}
void dijkstra(int k) {
    std::priority_queue<Pair> Q;
    memset(dis[k], 0x3f, sizeof dis[k]);
    dis[k][s[k]] = 0, Q.push((Pair){0, s[k]});
    int cnt = 0;
    while (!Q.empty()) {
        int u = Q.top().y; Q.pop();
        if (vis[u] == k) continue;
        if (++cnt == n) break;
        vis[u] = k;
        for (int i = head1[u]; i; i = nxt1[i])
            if (dis[k][e1[i].v] > dis[k][u] + e1[i].w) {
                dis[k][e1[i].v] = dis[k][u] + e1[i].w;
                Q.push((Pair){dis[k][e1[i].v], e1[i].v});
            }
    }
}
void solve(int a, int b, int c, int d) {
    for (int u = 1; u <= n; ++u)
        for (int i = head1[u]; i; i = nxt1[i]) {
            int v = e1[i].v, w = e1[i].w;
            if (dis[a][u] + w + dis[b][v] == dis[a][s[b]] && dis[c][u] + w + dis[d][v] == dis[c][s[d]])
                adde2(u, v, w), ++dgr[v];
        }
    for (int i = 1; i <= n; ++i) if (!dgr[i]) Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        if (dis[0][u] > ans) ans = dis[0][u];
        for (int i = head2[u]; i; i = nxt2[i]) {
            if (dis[0][e2[i].v] < dis[0][u] + e2[i].w)
                dis[0][e2[i].v] = dis[0][u] + e2[i].w;
            if (--dgr[e2[i].v] == 0) Q.push(e2[i].v);
        }
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= 4; ++i) s[i] = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        adde1(u, v, w), adde1(v, u, w);
    }
    for (int i = 1; i <= 4; ++i) dijkstra(i);
    solve(1, 2, 3, 4), solve(1, 2, 4, 3);
    printf("%d\n", ans);
    return 0;
}