黑暗城堡

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1462 字

Dijkstra求最短路树，各点可选父亲数相乘

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1486
// 题意：N 点 M 边无向图，求满足「树上 1 到 i 的路径长等于全图最短路 D_i」的生成树个数，对 2^31-1 取模。
// 思路：先跑一次 Dijkstra 求出 D_i，再统计每个点 i 有多少个点 j 满足 D_j+w(j,i)=D_i，各点选择数相乘即为答案。
// 复杂度：O(N^2+M) 时间 / O(N^2) 空间
// 易错点：模数是 2^31-1 而非常用质数，中间结果必须用 long long；同一个点可能有多个合法的父亲要全部计入。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const long long INF = (1LL << 60);
const long long MOD = 2147483647LL;
long long w[MAXN][MAXN];
long long d[MAXN];
bool vis[MAXN];
int main(){
    int n, m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++) w[i][j] = INF;
        w[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        int x, y, l;
        cin >> x >> y >> l;
        if(l < w[x][y]) w[x][y] = w[y][x] = l;
    }
    for(int i = 1; i <= n; i++) d[i] = INF;
    d[1] = 0;
    for(int it = 1; it <= n; it++){
        int u = 0;
        for(int i = 1; i <= n; i++){
            if(!vis[i] && (u == 0 || d[i] < d[u])) u = i;
        }
        vis[u] = true;
        if(d[u] >= INF) break;
        for(int v = 1; v <= n; v++){
            if(w[u][v] < INF && d[u] + w[u][v] < d[v]) d[v] = d[u] + w[u][v];
        }
    }
    long long ans = 1;
    for(int i = 2; i <= n; i++){
        long long cnt = 0;
        for(int j = 1; j <= n; j++){
            if(j != i && w[j][i] < INF && d[j] + w[j][i] == d[i]) cnt++;
        }
        ans = ans * cnt % MOD;
    }
    cout << ans << '\n';
    return 0;
}

黑暗城堡

正文

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