dark♂城堡（233

题目描述

一个图，有n个节点，m条带权值无向边，构造一颗生成树，使得树上的点到根（1）的距离为该点到1的最短距离。输出符合条件的生成树的个数

答案模取\(2^{31}-1\)

输入输出格式略

数据范围 \(n<=1000\)

---

这道题如果不考虑时间优化的话，跑\(O(N^2)\)的dij是完全可以的；

如何统计个数？ 我们相当于把点i 连在所有比他到根的最短距离短的点上，并且判断是否合法。利用乘法原理计数就可以了。

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int map[1010][1010];int point[1010],dis[1010];bool vis[1010];const long long mode=(1LL<<31)-1;bool compare(const int &a,const int &b){    return dis[a]
        
         dis[j])&&!vis[j])                cur=j;        vis[cur]=true;        for(int j=1;j<=n;j++)            dis[j]=min(dis[j],dis[cur]+map[j][cur]);    }//n^2 的 dij    sort(point+1,point+1+n,compare);//point里存点的标号，然后按照dis排序    long long ans=1;    for(int i=2;i<=n;i++)    {        long long tot=0;        for(int j=1;j