题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2750
枚举每一个起点，通过该边的子树中有多少节点就知道本次它被经过几次了；
因为同一起点到该边的起点的最短路唯一。
但其实不是！就在于可以有长度相等的最短路！
所以暴力通过dis[cur]+edge[ i ].w==dis[ v ]?来判断该边是否在当前最短路中。
记录从根到该边起点有多少路径时要保证指向它的点都已赋过值，所以拓扑一下。
别忘了到处写上那个暴力判断！
关于rd，别忘了赋初值。只要每次赋rd[cur]=0就行了。其它会在更新dis时赋好。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define ll long long using namespace std; const int N=1505,M=5005,mod=1e9+7; int n,m,head[N],pre[N],dis[N],xnt,rd[N]; ll d1[N],d2[N],ans[M]; bool in[N]; queue<int> r; struct Edge{ int next,from,to,w; Edge(int n=0,int f=0,int t=0,int w=0):next(n),from(f),to(t),w(w) {} }edge[M]; void spfa(int cur) { memset(dis,1,sizeof dis); queue<int> q; dis[cur]=0;q.push(cur);in[cur]=1;rd[cur]=0;// while(q.size()) { int k=q.front();q.pop();in[k]=0; for(int i=head[k],v;i;i=edge[i].next) { if(dis[k]+edge[i].w==dis[v=edge[i].to])rd[v]++; if(dis[k]+edge[i].w<dis[v=edge[i].to]) { rd[v]=1; dis[v]=dis[k]+edge[i].w; if(!in[v])q.push(v),in[v]=1; } } } } void dp(int cur) { d2[cur]=1; for(int i=head[cur],v;i;i=edge[i].next) if(dis[v=edge[i].to]==dis[cur]+edge[i].w) { if(!d2[v=edge[i].to])dp(v); (d2[cur]+=d2[v])%=mod; } } void tp(int cur) { r.push(cur); for(int i=head[cur],v;i;i=edge[i].next) if(dis[v=edge[i].to]==dis[cur]+edge[i].w)// { rd[v=edge[i].to]--; if(!rd[v])tp(v); } } void solve(int cur) { // printf("cur=%d\n",cur); memset(d1,0,sizeof d1); memset(d2,0,sizeof d2); while(r.size())r.pop(); spfa(cur); tp(cur); dp(cur); d1[cur]=1; while(r.size()) { int k=r.front();r.pop(); for(int i=head[k],v;i;i=edge[i].next) if(dis[v=edge[i].to]==dis[k]+edge[i].w) (d1[v]+=d1[k])%=mod; } for(int i=1,u,v;i<=m;i++) if(dis[u=edge[i].from]+edge[i].w==dis[v=edge[i].to])// { (ans[i]+=d1[u]*d2[v])%=mod; // printf("from=%d to=%d t=%lld ans=%lld\n",edge[i].from,edge[i].to,d2[edge[i].to],ans[i]); } } int main() { scanf("%d%d",&n,&m);int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); edge[++xnt]=Edge(head[x],x,y,z);head[x]=xnt; } for(int i=1;i<=n;i++) solve(i); for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; }
转载于:https://www.cnblogs.com/Narh/p/8870576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101716.html原文链接：https://javaforall.net
