『算法-ACM 竞赛-图论』信息奥赛一本通 1486： CH 6202 黑暗城堡 最短路径生成树计数

1486：黑暗城堡

【题目描述】
知道黑暗城堡有 N 个房间，M 条可以制造的双向通道，以及每条通道的长度。

城堡是树形的并且满足下面的条件：

设 Di 为如果所有的通道都被修建，第 i 号房间与第 1 号房间的最短路径长度；

而 Si 为实际修建的树形城堡中第 i 号房间与第 1 号房间的路径长度；

要求对于所有整数 i(1≤i≤N)，有 Si=Di 成立。

你想知道有多少种不同的城堡修建方案。当然，你只需要输出答案对 231−1 取模之后的结果就行了。

【输入】
第一行为两个由空格隔开的整数 N,M;

第二行到第 M+1 行为 3 个由空格隔开的整数 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
【提示】
样例说明

一共有 4 个房间，6 条道路，其中 1 号和 2 号，1 号和 3 号，1 号和 4 号，2 号和 3 号，2 号和 4 号，3 号和 4 号房间之间的通道长度分别为 1，2，3，1，2，1。

而不同的城堡修建方案数对 231−1 取模之后的结果为 6。

数据范围:

对于全部数据，1≤N≤1000，1≤M≤N(N−1)2,1≤l≤200。

#include<iostream>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define read(x) scanf("%lld",&x)
#define Read(x,y) scanf("%lld%lld",&x,&y)
#define gc(x)  scanf(" %c",&x);
#define mmt(x,y)  memset(x,y,sizeof x)
#define write(x) printf("%d\n",x)
#define INF 0x3f3f3f3f
#define ll long long
#define mod  ((1LL<<31) - 1LL)
const  ll N = 1005;
const ll M = 1e6;
ll d[N];
bool vis[N];ll id[N];
ll head[N],tot;
ll w[N][N];
struct Edge
{
    ll next;
    ll to;
    ll dis;
}edge[M*2];
inline void add(ll from,ll to,ll dis)
{
    edge[++tot].next = head[from];
    edge[tot].to = to;
    edge[tot].dis = dis;
    head[from] = tot;
}
void spfa()
{
    mmt(d,0x3f);
    mmt(vis,0);
    d[1] = 0;
    queue<ll> Q;
    Q.push(1);
    vis[1] = 1;
    while(Q.size())
    {
        ll x=  Q.front();
        Q.pop();
        vis[x] = 0;
        for(ll i = head[x];~i;i = edge[i].next)
        {
            ll y = edge[i].to;
            ll dis = edge[i].dis;
            if(d[y] > d[x] + dis){
                d[y] = d[x ]+dis;
                if(!vis[y]){
                    vis[y] = 1;
                    Q.push(y);
                }
            }
        }
    }
}
bool cmp(ll a,ll b)
{
    return d[a] < d[b];
}
void init()
{
    mmt(head,-1);
    tot = 0;
    for(int i = 1;i <=1000;++i){
        for(int j = 1;j <= 1000;++j){
            w[i][j] = INF;
        }
        w[i][i] = 0;
    }
}
int main()
{
    init();
    ll n,m;
    ll f,t,dis;
    Read(n,m);
    for(ll i = 1;i <= m;++i){
        Read(f,t);read(dis);
        if(w[f][t] > dis)  w[f][t] = w[t][f] = dis;
        add(f,t,dis);
        add(t,f,dis);
    }
    spfa();//先跑一次最短路，求出d数组 dijkstra也可以
    for(ll i = 1;i <= n;++i)  id[i] = i;
    sort(id +1 ,id + n+1,cmp);//按d[ ]从小到大排序
    ll ans = 1;
    ll cnt = 0;
    for(ll i = 2;i <= n;++i){
        cnt = 0;
        for(ll j = 1;j <= i-1;++j){//模拟最短路径树形成的过程，并按乘法原理统计方案数，
            if(d[id[i]] == d[id[j]] + w[id[j]][id[i]]) cnt ++;
        }
         ans = ans * cnt %mod;
    }
     cout<<ans<<endl;
}