题目描述

黑暗城堡

在顺利攻破Lord lsp的防线之后，lqr一行人来到了Lord lsp的城堡下方。

Lord lsp黑化之后虽然拥有了强大的超能力，能够用意念力制造建筑物，但是智商水平却没怎么增加。

现在lqr已经搞清楚黑暗城堡有N个房间，M条可以制造的双向通道，以及每条通道的长度。

lqr深知Lord lsp的想法，为了避免每次都要琢磨两个房间之间的最短路径，Lord lsp一定会把城堡修建成树形的。

但是，为了尽量提高自己的移动效率，Lord lsp一定会使得城堡满足下面的条件：

设 D[i] 为如果所有的通道都被修建，第 i 号房间与第1号房间的最短路径长度；而 S[i] 为实际修建的树形城堡中第 i 号房间与第1号房间的路径长度；要求对于所有整数 i，有 S[i]=D[i] 成立。

为了打败Lord lsp，lqr想知道有多少种不同的城堡修建方案。

你需要输出答案对 231–1 取模之后的结果。

输入格式
第一行有两个整数 N 和 M。

之后 M 行，每行三个整数X，Y 和L，表示可以修建 X 和 Y 之间的一条长度为 L 的通道。

输出格式
一个整数，表示答案对 231–1 取模之后的结果。

数据范围
2≤N≤1000,
N−1≤M≤N(N−1)/2,
1≤L≤100
输入样例：
3 3
1 2 2
1 3 1
2 3 1
输出样例：
2
由题可知，即给出n个点m条边求最小生成树的组成方案有多少。

那么只需要在Prim的基础上增加一个sum数组，记录有几个点可以到v，最后把sum数组累乘就好了。

结合图示：

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e3+5,p=(1<<31)-1;
ll ans=1,sum[N];
int n,m,d[N];
bool vis[N];
struct t_
{
    int v,w;
};
deque<t_>nxt[N];

void Prim()
{
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    sum[1]=1;

    for(int k=1;k<n;++k)
    {
        int u=0;
        for(int i=1;i<=n;++i)
        if(!vis[i]&&d[i]<d[u]) u=i;

        vis[u]=1;

        for(int i=0;i<nxt[u].size();++i)
        {
            int v=nxt[u][i].v,w=nxt[u][i].w;
            if(!vis[v])
            {
                if(d[v]==d[u]+w) sum[v]++;
                else
                if(d[v]>d[u]+w) d[v]=d[u]+w,sum[v]=1;
            }
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1,u,v,w;i<=m;++i)
    {
        scanf("%d %d %d",&u,&v,&w);
        nxt[u].push_back((t_){v,w});
        nxt[v].push_back((t_){u,w});
    }
    Prim();
    for(int i=1;i<=n;++i)
    ans=(ans*sum[i])%p;
    printf("%d",ans);
}