题解：P10929 黑暗城堡

· · 题解

题目要求我们建的树满足 D_i = S_i ，容易想到用其他路径代替最短路中的路径。

例：

很明显，如果两条红边的长等于黑边的长，那么这条黑边就可以被两条红边代替。

所以我们跑一遍最短路，然后 O (n ^ 2) 统计答案。答案就是叶节点到根节点最短路径数量的积。

注意：堆的重载运算符别写错啦。

code：

# include <bits/stdc++.h>
# define int __int128
using namespace std;
int mp[1011][1011];
int n, m;
struct path
{
    int v, w;
    path (int v = 0, int w = 0) :
        v (v), w (w) {}
};
vector <path> e[100012];
int dis[1011];
struct node
{
    int u, w;
    node (int u = 0, int w = 0) :
        u (u), w (w) {}
    bool operator < (const node &b) const
    {
        return w > b.w;
    }
};
priority_queue <node> q;
bool vis[1011];
void dijkstra (int st)
{
    for (int i = 1; i <= n; i ++) dis[i] = 1e18, vis[i] = 0;
    dis[st] = 0;
    q.push (node (st, 0));
    while (not q.empty ())
    {
        int u = q.top ().u;
        q.pop ();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto it : e[u])
        {
            int v = it.v, w = it.w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                q.push (node (v, dis[v]));
            }
        }
    }
}
# define stdi stdin
# define stdo stdout
int ans = 0;
int mod = (1 << 31) - 1;
signed main()
{
    freopen ("dark.in", "r", stdin);
    freopen ("dark.out", "w", stdout);
    setvbuf (stdi, (char*) calloc (1 << 20, sizeof (char)), _IOFBF, 1 << 20);
    setvbuf (stdo, (char*) calloc (1 << 20, sizeof (char)), _IOFBF, 1 << 20);
    memset (mp, 0x3f, sizeof (mp));
    scanf ("%lld %lld", &n, &m);
    for (int i = 1; i <= m; i ++)
    {
        int u, v, w;
        scanf ("%lld %lld %lld", &u, &v, &w);
        e[u].push_back (path (v, w));
        e[v].push_back (path (u, w));
        mp[u][v] = mp[v][u] = min (mp[u][v], w);
    }
    dijkstra (1);
    ans = 1;
    for (int i = 2; i <= n; i ++)
    {
        int sum = 0;
        for (int j = 1; j <= n; j ++)
        {
            sum += ((dis[j] + mp[i][j]) == dis[i]);
        }
        if (sum > 0) ans = (ans * sum) % mod;
    }
    printf ("%lld\n", ans);
}