题解 | #黑暗城堡#

solution

最短路 + 最小生成树 $\Rightarrow \backslash Rightarrow$ 最短路径生成树

题目要求很明确，求出有多少棵最短路径生成树。 关于最短路径生成树请点击[这里][8]。简要概括一下，最短路径生成树就是对于树中的任意一对父子节点 $f,sf\; ,\; s$ ，$di{s}_s=di{s}_f+wdis\_s\; =\; dis\_f\; +\; w$ ， $ww$ 为（f , s) 边的权值。所以针对此题来说，我们完全可以先求出起点到各个节点的最短路路径和 $di{s}_{i}dis\_i$ ,然后暴力的去枚举每个节点，枚举这个节点连出的所有边，如果满足 $di{s}_s=di{s}_f+wdis\_s\; =\; dis\_f\; +\; w$ ，$cn{t}_{s}cnt\_s$++ , 其含义就为当前节点可供选择的方案数。因为对于任何一个节点 $ii$ 选择 $cn{t}_{i}cnt\_i$ 中的任何一中方案都可以构成最短路径生成树， 所以根据乘法原理累乘起来的结果就为最终答案。 （虽然我没用到最小生成树，但用 $primprim$ 算法同样是可以做出来的……）

code

using Simon O_O ;
int n , m , cnt ;
int ans = 1 ; 
int head[maxn] , Cnt[maxn] , dis[maxn] ; 
bool pd[maxn] ; 
struct node 
{
	int frm , to , nxt , dis ;
} ed[maxn << 1] ;
void add(int u , int v , int w )
{
	ed[++cnt] = {u , v , head[u] , w} ; 
	head[u] = cnt ; 
}
void dij()
{
	priority_queue<pii , vector<pii> , greater<pii> > q ;
	memset(dis , 0x3f , sizeof(dis)) ;
	dis[1] = 0 ;	q.push({0 , 1}) ; 
	while( ! q.empty() )
	{
		int u = q.top().second ;
		q.pop() ;     
		if(pd[u])	continue ; 	pd[u] = true ; 
		for(int i = head[u] ; i ; i = ed[i].nxt)
		{
			int v = ed[i].to , w = ed[i].dis ;
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w ; 
				q.push({dis[v] , v}) ; 
			}
		}
	}
}
signed main()
{
	n = read() , m = read() ; 
	while( m-- )
	{
		int u = read() , v = read() , w = read()  ;
		add(u , v , w) , add(v , u , w) ;
	}
	dij() ;

	for(int i = 1 ; i <= n ; i++ )
		for(int j = head[i] ; j ; j = ed[j].nxt )
		{
			int v =  ed[j].to , w = ed[j].dis ; 
			if(dis[v] == dis[i] + w) Cnt[v]++ ; 
		}

	for(int i = 1 ;i <= n ; i++ )
		if(Cnt[i])	ans = ans * Cnt[i] % Mod ;
	cout << ans ; 
	return 0 ; 
}