黑暗城堡

AcWing-349-黑暗城堡

分析

见《进阶指南》第369页。

实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1010, M = (1ll << 31) - 1;
int n, m;
int g[N][N], dis[N];
bool mark[N];
int a[N];

void dijkstra () {
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    
    for (int k = 1; k <= n - 1; ++ k) {
        int cur = -1;
        for (int i = 1; i <= n; ++ i)
            if (mark[i] == false && (cur == -1 || dis[i] < dis[cur]))
                cur = i;
        mark[cur] = true;

        for (int i = 1; i <= n; ++ i) {
            if (mark[i] == true) continue;
            dis[i] = min(dis[i], dis[cur] + g[cur][i]);
        }
    }
}
bool cmp (const int& a, const int& b) {
    return dis[a] < dis[b];
}

int main () {
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= 1000; ++ i) g[i][i] = 0;
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; ++ i) {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }

    dijkstra();
    for (int i = 1; i <= n; ++ i) a[i] = i;
    sort(a + 1, a + n + 1, cmp);
    LL res = 1;
    for (int i = 2; i <= n; ++ i) {
        int cnt = 0;
        for (int j = 1; j <= i - 1; ++ j)
            if (dis[a[i]] == dis[a[j]] + g[a[j]][a[i]])
                ++ cnt;
        res = res * cnt % M;
    }
    cout << res << endl;
    return 0;
}