首页 > 代码库 > 城堡 （spfa+cheng）
城堡 （spfa+cheng）
【问题描述】
给定一张?个点?条边的无向连通图，每条边有边权。我们需要从?条边中
选出? − 1条， 构成一棵树。 记原图中从 1 号点到每个节点的最短路径长度为? ? ，
树中从 1 号点到每个节点的最短路径长度为? ? ，构出的树应当满足对于任意节点
?，都有? ? = ? ? 。
请你求出选出? − 1条边的方案数。
【输入格式】
输入的第一行包含两个整数?和?。
接下来?行，每行包含三个整数?、?和?，描述一条连接节点?和?且边权为
?的边。
【输出格式】
输出一行，包含一个整数，代表方案数对2 31 − 1取模得到的结果。
【样例输入】
3 3
1 2 2
1 3 1
2 3 1
【样例输出】
2
【数据规模和约定】
32 ≤ ? ≤ 5，? ≤ 10。
对于50%的数据，满足条件的方案数不超过 10000。
对于100%的数据，2≤ ? ≤ 1000，? − 1 ≤ ? ≤
? ?−1
2
，1 ≤ ? ≤ 100。
思路：
按照题目里的说的模拟
先跑一遍spfa得出单源最短路
然后对于每一个点枚举所有与它相连的点
如果与它相连的点的dis值加上这条边的权值等于它的dis值
则这个点的价值加一
所有的点枚举完后
把价值为0的点赋值为1
然后所有点的价值相乘
即可得出答案
但是
你以为这就是正解？
别忘了取mod（因为这个我没了40分）
有mod才是正解
来，上代码：
#include<queue>#include<cstdio>#include<cstring>#include<iostream>using namespace std;struct node { int from,to,dis,next;};struct node edge[1000005];const long long int mod=2147483647;int num_head,num_edge,num_1=0,head[1001];int dis_1[1001],tree_leaf[1001],num_leaf=1;long long int ans_edge=1;long long int num_edge_tree[1001];char word;bool if_in_tree[1001];queue<int>q;inline void edge_add(int from,int to,int dis){ num_1++; edge[num_1].to=to; edge[num_1].dis=dis; edge[num_1].from=from; edge[num_1].next=head[from]; head[from]=num_1;}inline void read_int(int &now_001){ now_001=0;word=getchar(); while(word>‘9‘||word<‘0‘) word=getchar(); while(word>=‘0‘&&word<=‘9‘) { now_001=now_001*10+(int)(word-‘0‘); word=getchar(); }}void map_spfa(){ bool if_in_spfa[1001]; memset(dis_1,127/3,sizeof(dis_1)); memset(if_in_spfa,false,sizeof(if_in_spfa)); dis_1[1]=0; if_in_spfa[1]=true; q.push(1); int cur_1,cur_2; while(!q.empty()) { cur_1=q.front(); for(int i=head[cur_1];i!=0;i=edge[i].next) { if(dis_1[cur_1]+edge[i].dis<dis_1[edge[i].to]) { dis_1[edge[i].to]=dis_1[cur_1]+edge[i].dis; if(!if_in_spfa[edge[i].to]) { q.push(edge[i].to); if_in_spfa[edge[i].to]=true; } } } if_in_spfa[cur_1]=false; q.pop(); }}int main(){ read_int(num_head),read_int(num_edge); int from,to,dis; for(int i=1 ; i<=num_edge ; i++) { read_int(from),read_int(to),read_int(dis); edge_add(from,to,dis); edge_add(to,from,dis); } map_spfa(); for(int j=1;j<=num_head;j++) { for(int i=head[j];i!=0;i=edge[i].next) { if(edge[i].dis+dis_1[j]==dis_1[edge[i].to]) { num_edge_tree[edge[i].to]++; num_edge_tree[edge[i].to]%=mod; } } } for(int i=1;i<=num_head;i++) if(num_edge_tree[i]==0) num_edge_tree[i]=1; for(int i=1;i<=num_head;i++) { ans_edge*=num_edge_tree[i]; ans_edge%=mod; } cout<<ans_edge<<endl; return 0;}
城堡 （spfa+cheng）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。