陈杉菜 于 2019-08-01 20:32:12 发布以下是我今天解题的题解报告：
[1] 黑暗城堡
题目描述
你知道黑暗城堡有N个房间（1≤N≤1000），M条可以制造的双向通道，以及每一条通道的长度。
城堡是树形的并且满足以下条件：如果所有的通道都被修建，设D[i]为第i号房间与第一号房间的最短路径长度；而S[i]为实际修建的树形城堡中第i号房间与第1号房间的路径长度；要求对于所有整数i（1≤i≤N），有S[i]=D[i]成立。
你想知道有多少种；不同的城堡修建放啊。当然，你只需要输出答案对 231 – 1 取模之后的结果就行了。
输入
第一行有两个整数 N 和 M。
之后 M 行，每行三个整数 X，Y 和 L，表示可以修建 X 和 Y 之间的一条长度为 L 的通道。
输出
输出一个整数，表示答案对 231 – 1 取模之后的结果。
样例输入
4 6
1 2 1
1 3 2
1 4 3
2 3 1
2 4 2
3 4 1
样例输出
6
题目类型：
最小生成树 链接矩阵
思路：
见代码
#include<bits/stdc++.h> #define inf 1e12; using namespace std; int n,m; long long dis[1010][1010],g[20000],cnt[20000]; bool vis[2000000]={ 0}; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)//一、预处理 { if(i==j) dis[i][j]=0; else dis[j][i]=dis[i][j]=inf; } int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); if(dis[x][y]>z) { dis[x][y]=z;dis[y][x]=z;//注意这一步判断 } } for(int i=1;i<=n;i++) { g[i]=dis[1][i]; } for(int i=1;i<=n;i++)// 二、用迪杰斯特拉算法求出一号房间到每个房间的单源最短路 { long long minn=inf; int u; for(int j=1;j<=n;j++) { if(!vis[j]&&minn>g[j]) { minn=g[j]; u=j; } } vis[u]=1; for(int j=1;j<=n;j++) { if(g[j]>dis[u][j]+g[u]) { g[j]=g[u]+dis[u][j]; } } } long long ans=1; for(int i=1;i<=n;i++)//三、方案累加 { for(int j=1;j<=n;j++) { if(i!=j&&g[j]==g[i]+dis[i][j]) cnt[j]++; } } for(int i=1;i<=n;i++) { if(cnt[i
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
