【问题描述】

给定一张?个点?条边的无向连通图，每条边有边权。我们需要从?条边中

选出? − 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
     
      #include
      
       #include
       
        #include
        
         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
         
          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