路径方案数（mod）

[题目描述]

给一张无向图，n 个点和 m 条边，cyb 在 1 号点，他要去 2 号点，

cyb 可以从 a 走到 b，当且仅当a到2的最短路，比b 到2的最短路长。

求 cyb 的路径方案数

两条路径不同,当且仅当将两条路径中依次经过的边的编号不完全相同，

图可能会有重边；

由于答案可能很大，

只需要输出答案对于 10^9+9 取模的值即可

[输入文件]

第一行两个正整数 n,m

接下来 m 行

每行 x，y，z 表示有一条边，长度为 z，链接了 x，y

[输出文件]

一个正整数表示答案

[输入样例1]                                          [输入样例2]

5 6                                                         7 8

1 3 2                                                      1 3 1

1 4 2                                                      1 4 1

3 4 3                                                      3 7 1

1 5 12                                                    7 4 1

4 2 34                                                    7 5 1

5 2 24                                                    6 7 1

5 2 1

6 2 1

[输出样例 1]                                         [输出样例 2]

2                                                          4

[数据范围]

30%：   N<=100，M<=1000

100%： N<=50000，,M<=100000

每条边的长度<=1000

题解：

首先处理出每个点到2的距离，重新建图，跑一遍拓扑排序，注意一下统计路径数量就可以了。

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define mod (1000000009)using namespace std;typedef long long lol;lol n,m;struct node{lol next,to,dis;}edge[200005];struct Map{lol from,to;}map[100005];lol head[50005],size=1;void putin(lol from,lol to,lol dis){size++;edge[size].next=head[from];edge[size].to=to;edge[size].dis=dis;head[from]=size;}lol gi(){ lol ans=0,f=1; char i=getchar(); while(i<'0'||i>'9'){ if(i=='-')f=-1;i=getchar();} while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();} return ans*f;}lol dist[50005];bool vis[50005];void SPFA(lol r){ lol i,j; memset(dist,127/3,sizeof(dist)); queue
            
             mem; dist[r]=0; vis[r]=1; mem.push(r); while(!mem.empty()) { lol x=mem.front();mem.pop(); vis[x]=0; for(i=head[x];i!=-1;i=edge[i].next) { lol y=edge[i].to; if(dist[y]>dist[x]+edge[i].dis) { dist[y]=dist[x]+edge[i].dis; if(!vis[y]) { mem.push(y); vis[y]=1; } } } }}lol in[50005];void make(){ lol i; memset(head,-1,sizeof(head)); size=1; for(i=1;i<=m;i++) { if(dist[map[i].from]>dist[map[i].to])putin(map[i].from,map[i].to,1),in[map[i].to]++; else if(dist[map[i].from]
             
              mem; ans[r]=1; for(i=1;i<=n;i++) if(!in[i]) { mem.push(i); vis[i]=1; } while(!mem.empty()) { lol x=mem.front();mem.pop(); vis[x]=0; for(i=head[x];i!=-1;i=edge[i].next) { lol y=edge[i].to; ans[y]=(ans[y]+ans[x])%mod; in[y]--; if(!in[y]&&!vis[y])mem.push(y),vis[y]=1; } }}int main(){ lol i,j; n=gi();m=gi(); memset(head,-1,sizeof(head)); for(i=1;i<=m;i++) { lol from=gi(),to=gi(),dis=gi(); map[i].from=from;map[i].to=to; putin(from,to,dis); putin(to,from,dis); } SPFA(2); make(); solve(1); printf("%lld",ans[2]); return 0;}