最短路径生成树

简介

1. 最短路径生成树是一棵树，它的根节点为S，在这棵树上跑最短路与在原图上跑得到的d会是完全一样的。
2. 所以跑最短路再瞎搞就行了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define mid ((st[x].l+st[x].r)>>1)
#define ll long long
#define rint register int
#define mp(x,y) make_pair(x,y)
using namespace std;
template<typename xxx>void read(xxx &x)
{
    x=0;int f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x*=f;
}
template<typename xxx>void print(xxx x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int mod=2147483647;
const int maxn=500080;
const int inf=0x7fffffff;
struct edge{
    int last,to,val;
}e[maxn<<1];
int tot,head[maxn];
inline void add(int from,int to,double val)
{
    ++tot;
    e[tot].to=to;
    e[tot].val=val;
    e[tot].last=head[from];
    head[from]=tot;
}
int n,m;
queue<int>q;
ll cnt[maxn];
int dis[maxn],vis[maxn];
inline void spfa(int x)
{
    for(rint i=0;i<=n;++i) dis[i]=inf;
    q.push(1);dis[1]=0;
    while(q.size())
    {
        int x=q.front();q.pop();
        vis[x]=0;
        for(rint i=head[x];i;i=e[i].last)
        {
            if(dis[e[i].to]>dis[x]+e[i].val)
            {
                dis[e[i].to]=dis[x]+e[i].val;
                if(!vis[e[i].to])
                {
                    vis[e[i].to]=1;
                    q.push(e[i].to);
                }
            }
        }
    }
}
int main()
{
    int a,b,c;
    read(n);read(m);
    for(rint i=1;i<=m;++i)
    {
        read(a);read(b);read(c);
        add(a,b,c);add(b,a,c);
    }
    spfa(1);ll ans=1;
    for(rint x=1;x<=n;++x)
        for(rint i=head[x];i;i=e[i].last)
            if(dis[e[i].to]==dis[x]+e[i].val)
                ++cnt[e[i].to];
    for(rint i=2;i<=n;++i) ans=ans*cnt[i]%mod;
    print(ans);
    return 0;
}
/*
最短路径生成树
我们枚举每条边，对于一条边 (i,j)，如果 di+w(i,j)=dj,那这条边就可以被选，就 ++cnt[j]，代表可以到达j的路径可以增加一条
统计时把除1外所有cnt[]相乘
*/