首页 > 代码库 > 最短树

最短树

技术分享

技术分享

源代码:#include<cstdio>#include<cstring>#include<queue>#define LL long long#define INF 2147483647 //竟然没注意到取模。using namespace std;queue <LL> Q;LL n,m,Num(0),Ans=1,Sum[1000001];LL i[1000001],Head[1000001];bool In[1000001]={0};struct Node{    LL S,To,Next;}Edge[2000001];void Add(LL t1,LL t2,LL t){    Edge[++Num].S=t;    Edge[Num].To=t2;    Edge[Num].Next=Head[t1];    Head[t1]=Num;}void SPFA(){    memset(i,0x3f,sizeof(i));    i[1]=0;    In[1]=true;    Q.push(1);    while (!Q.empty())    {        LL t=Q.front();        Q.pop();        In[t]=false;        for (LL a=Head[t];a;a=Edge[a].Next)        {            LL T=Edge[a].To;            if (i[T]>i[t]+Edge[a].S)            {                    i[T]=i[t]+Edge[a].S;                if (!In[T])                {                    In[T]=true;                    Q.push(T);                }            }        }    }}int main() //图论题还是得灵活。{    scanf("%I64d%I64d",&n,&m);    for (LL a=1;a<=m;a++)    {        LL t,t1,t2;        scanf("%I64d%I64d%I64d",&t1,&t2,&t);        Add(t1,t2,t);        Add(t2,t1,t);    }    SPFA();    Q.push(1);    In[1]=true;    Sum[1]=1;    while (!Q.empty()) //类SPFA的BFS。    {        LL t=Q.front();        Q.pop();        for (LL a=Head[t];a;a=Edge[a].Next)        {            LL T=Edge[a].To;            if (i[T]==i[t]+Edge[a].S)              Sum[T]++;            if (Sum[T]>=INF) //取模优化。              Sum[T]-=INF;            if (!In[T])            {                In[T]=true;                Q.push(T);            }        }    }    for (LL a=1;a<=n;a++) //乘法计数原理。    {        Ans*=Sum[a];        if (Ans>=INF) //取模优化。          Ans%=INF;    }    printf("%I64d",Ans);    return 0;}/*    两三个点也许不会构成一棵真正的树,但想想,只要是囊括了所有节点,就一定会构成一棵树!    想到这里,SPFA+BFS统计边数,再乘法计数即可。*/

最短树