首页 > 代码库 > 最短树
最短树
源代码:#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统计边数,再乘法计数即可。*/
最短树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。