相遇 题解

题目大意

无向带权图，喵星人从 $S$ 沿某条最短路径走向 $T$，汪星人同时从 $T$ 沿某条最短路径走向 $S$，速度相同。求最短路径长度，以及"两人路线始终不相遇（既不同时在某点、也不同时在某边）"的路线组合数。

算法思路

1. 最短路：从 $S$、$T$ 各跑一次 Dijkstra，得到 $dis1[]$、$dis2[]$，最短路径长 $D=dis1[T]$。

2. 路径计数：把"最短路 DAG"建出来（边 $(u,v)$ 属于最短路 DAG 当且仅当 $dis1[u]+w=dis1[v]$）。在 DAG 上按拓扑序 DP，得到 $f[u]$ = 从 $S$ 到 $u$ 的最短路径条数；对称地得到 $g[u]$ = 从 $T$ 到 $u$ 的最短路径条数。

3. 容斥：总的路线组合数 = $f[T]\times g[S]$。两人相遇的位置是唯一的"中点"（因为速度相同、都走最短路径）。减去相遇的组合：

   • 若 $D$ 为偶数，在中点顶点 $u$（$2\,dis1[u]=D$ 且 $2\,dis2[u]=D$）相遇，减去 $(f[u]\cdot g[u])^2$；
   • 若 $D$ 为奇数，在中点边 $(u,v)$（$2\,dis1[u]<D<2\,dis1[v]$ 且 $2\,dis2[v]<D<2\,dis2[u]$）相遇，减去 $(f[u]\cdot g[v])^2$。

复杂度

Dijkstra $O((n+m)\log n)$，DP $O(n+m)$。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, S, T;
    cin >> n >> m >> S >> T;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    auto dijkstra = [&](int src, vector<ll> &dis) {
        dis.assign(n + 1, INF);
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        dis[src] = 0;
        pq.push({0, src});
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d != dis[u]) continue;
            for (auto [v, w] : g[u]) {
                if (dis[v] > d + w) {
                    dis[v] = d + w;
                    pq.push({dis[v], v});
                }
            }
        }
    };
    vector<ll> dis1, dis2;
    dijkstra(S, dis1);
    dijkstra(T, dis2);
    ll D = dis1[T];

    // 最短路 DAG 与路径计数
    vector<vector<int>> dag1(n + 1), dag2(n + 1);
    vector<int> indeg1(n + 1), indeg2(n + 1);
    for (int u = 1; u <= n; ++u)
        for (auto [v, w] : g[u]) {
            if (dis1[u] + w == dis1[v]) { dag1[u].push_back(v); ++indeg1[v]; }
            if (dis2[u] + w == dis2[v]) { dag2[u].push_back(v); ++indeg2[v]; }
        }
    auto count_paths = [&](vector<vector<int>> &dag, vector<int> indeg, int src, vector<ll> &cnt) {
        cnt.assign(n + 1, 0);
        cnt[src] = 1;
        queue<int> q;
        for (int u = 1; u <= n; ++u) if (indeg[u] == 0) q.push(u);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : dag[u]) {
                cnt[v] += cnt[u];
                if (--indeg[v] == 0) q.push(v);
            }
        }
    };
    vector<ll> cnt1, cnt2;
    count_paths(dag1, indeg1, S, cnt1);  // cnt1[u] = S 到 u 的最短路条数
    count_paths(dag2, indeg2, T, cnt2);  // cnt2[u] = T 到 u 的最短路条数

    ll ans = cnt1[T] * cnt2[S];
    for (int u = 1; u <= n; ++u) {
        if (2 * dis1[u] == D && 2 * dis2[u] == D) {
            ans -= cnt1[u] * cnt2[u] * cnt1[u] * cnt2[u];
        } else {
            for (int v : dag1[u]) {
                if (2 * dis1[u] < D && 2 * dis1[v] > D && 2 * dis2[v] < D && 2 * dis2[u] > D) {
                    ans -= cnt1[u] * cnt2[v] * cnt1[u] * cnt2[v];
                }
            }
        }
    }
    cout << D << '\n' << ans << '\n';
    return 0;
}