#10064. 「一本通 3.1 例 1」黑暗城堡-Toy模板网

这篇具有很好参考价值的文章主要介绍了#10064. 「一本通 3.1 例 1」黑暗城堡。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

题目描述

你知道黑暗城堡有 N 个房间，M 条可以制造的双向通道，以及每条通道的长度。
城堡是树形的并且满足下面的条件：
设 $D_i$ 为如果所有的通道都被修建，第 i 号房间与第 1 号房间的最短路径长度；
而 $S_i$ 为实际修建的树形城堡中第 i 号房间与第 1 号房间的路径长度；
要求对于所有整数 i ( $1\le i\le N$ )，有 $S_i= D_i$ 成立。
你想知道有多少种不同的城堡修建方案。当然，你只需要输出答案对 $2^{31} -1$ 取模之后的结果就行了。

输入格式

第一行为两个由空格隔开的整数 N, M;
第二行到第 M+1 行为 3 个由空格隔开的整数 x, y, l：表示 x 号房间与 y 号房间之间的通道长度为 l。

输出格式

一个整数：不同的城堡修建方案数对 $2^{31} -1$ 取模之后的结果。

样例

输入

输出

代码详解

思路

Dijsktra求最短路，由乘法原理可得ACcode文章来源地址https://www.toymoban.com/news/detail-558301.html

ACcode

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1005;
const int mod=(1<<31)-1;
int w[maxn][maxn],dis[maxn];
bool vis[maxn];
int n,m;
long long sum;
void Dij(){
	dis[1]=0;
	for(int i=1;i<=n;i++){
		int e=0;
		for(int j=1;j<=n;j++){ if(!vis[j]&&(!e||dis[j]<=dis[e])) e=j; }
		vis[e]=1;
		for(int j=1;j<=n;j++){ if(!vis[j]) dis[j]=min(dis[j],dis[e]+w[e][j]); }
	}
}
int main(){
	memset(dis,INF,sizeof(dis));
	memset(w,INF,sizeof(w));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,ww;
		cin>>u>>v>>ww;
		w[u][v]=w[v][u]=ww;
	}
	Dij();
	sum=1;
	int ans;
	for(int i=2;i<=n;i++){
		ans=0;
		for(int j=1;j<=n;j++) if(dis[i]==dis[j]+w[j][i]&&dis[i]!=INF) ans++;
		sum=sum*ans%mod;
	}
	cout<<sum;
	return 0;
}