路径方案数
[题目描述]
给一张无向图，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]
5 6
1 3 2
1 4 2
3 4 3
1 5 12
4 2 34
5 2 24
[输出样例 1]
2
[输入样例 2]
7 8
1 3 1
1 4 1
3 7 1
7 4 1
7 5 1
6 7 1
5 2 1
6 2 1
[输出样例 2]
4
[数据范围]
30%： N<=100，M<=1000
100%： N<=50000，,M<=100000
每条边的长度<=1000
分析：
上午考试我是真的不知道在干什么，这个基本的最短路然后重建边再拓扑也没看出来。。。
spfa以2为起点跑一遍，然后按照要求重建边再跑拓扑即可。但是有一个问题，因为重建边后1的入度可能不为0，那么就反向建边，因为可以保证2的入度一定为0。然后跑拓扑就行了。
Code：
//It is made by HolseLee on 20th July 2018 //mod #include<bits/stdc++.h> using namespace std; const int N=5e4+7; const int M=2e5+7; const int mod=1e9+9; int n,m,v[N],head[N],size; int dis[N],dg[N],ans; bool vis[N],rx[M]; struct Node{ int to,next,val; }edge[M]; inline int read() { char ch=getchar();int num=0;bool flag=false; while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();} while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();} return flag?-num:num; } inline void add(int x,int y,int z) { edge[++size].to=y; edge[size].val=z; edge[size].next=head[x]; head[x]=size; } void spfa(int sta) { memset(dis,0x7f,sizeof(dis)); memset(vis,false,sizeof(vis)); queue<int>t;t.push(sta); dis[sta]=0;vis[sta]=true; while(!t.empty()){ int x=t.front();t.pop();vis[x]=false; for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[y]>dis[x]+edge[i].val){ dis[y]=dis[x]+edge[i].val; if(!vis[y])t.push(y),vis[y]=true; } } } } void remake() { for(int x=1;x<=n;x++){ for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[x]<dis[y]){ rx[i]=true;dg[y]++; } } } } void toplogic(int sta) { queue<int>t;t.push(sta); memset(v,0,sizeof(v)); v[sta]=1; while(!t.empty()){ int x=t.front();t.pop(); for(int i=head[x];i!=-1;i=edge[i].next){ if(rx[i]&&dg[edge[i].to]){ int y=edge[i].to;v[y]=(v[y]+v[x])%mod;--dg[y]; if(dg[y]==0)t.push(y); } } } } int main() { freopen("mod.in","r",stdin); freopen("mod.out","w",stdout); n=read();m=read();int x,y,z; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ x=read();y=read();z=read(); add(x,y,z);add(y,x,z);} spfa(2);remake();toplogic(2); printf("%d ",v[1]); return 0; }