首页 > 代码库 > 城堡 (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)