黑暗城堡（最小生成树）

传送门

解析

这道书上例题主要用Dijkstra算法解决，但是关键的一步是如何计算有多少种方案。

“统计有多少个节点满足x属于T,并且dis[p]=dis[x]+edge(x,p)”，其中edge表示边的长度。

根据乘法原理，我们把每一步统计出的数量乘起来，就得到了题目的结果。

#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]=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]==0) continue;
        ans*=cnt[i];
        ans%=2147483647;
    }
    cout<<ans;
}