算法竞赛进阶指南.黑暗城堡

题目

349. 黑暗城堡

算法标签: 最小生成树, 最短路算法, 最短路径树

思路

答案就是有多少棵最短路径树
什么是最短路径树?
最短路径树就是在图中通过算法选择的边作为最短路的边的树

上述图的以$1$号点为起点的最短路径树就是

在非负权图中, 选择的过程就是$dijkstra$算法的过程, 每次选择到$1$号点距离最小的点进行更新

代码

统计每个点可能被更新的次数, 根据乘法原理, 相乘就是能构成的树的数量

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int N = 1010, M = N * N, MOD = 2147483647;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
int d[N];
bool vis[N];

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx]=  head[u], w[idx] = val, head[u] = idx++;
}

void dijkstra() {
   
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<>> q;
    q.push({
   0, 1});

    while (!q.empty()) {
   
        auto [dis, u] = q.top();
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (d[u] + w[i] <= d[v]) {
   
                d[v] = d[u] + w[i];
                q.push({
   d[v], v});
            }
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }


    dijkstra();

    LL ans = 1;
    int cnt[N] = {
   0};
    for (int i = 1; i <= n; ++i) {
   
        for (int j = head[i]; ~j; j = ne[j]) {
   
            int v = ed[j];
            if (d[i] + w[j] == d[v]) cnt[v]++;
        }
    }

    for (int i = 1; i <= n; ++i) {
   
        if (cnt[i]) ans = ans * cnt[i] % MOD;
    }

    cout << ans << "\n";
    return 0;
}