容易想到枚举所有起点 做最短路 然后枚举边统计次数
一条边(x,y)的贡献 肯定是 s到x最短路的方案数 乘上 s到其他点但经过了y的最短路
对于前者
每个点可以从前一个点递推过来 只要满足dis[vis]==dis[now]+edge[u].val 当一个点被所有入边都统计了一次后 就可以搜他了（拓扑思想）
对于后者
每个点从后一个点递推过来
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define N 5505 #define M 5005 #define ll long long using namespace std; const int mod=1000000007; template <class T> inline void read(T &x) { x=0; static char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); } int n,m,first[N],tot,dis[N]; ll a[N],b[N],ans[N]; struct Edge { int from,to,next,val; }edge[M]; inline void addedge(int x,int y,int z) { tot++; edge[tot].from=x; edge[tot].to=y; edge[tot].next=first[x]; edge[tot].val=z; first[x]=tot; } bool visit[N],onroad[N]; typedef pair<int,int> Pair; void Dijkstra(int s) { priority_queue<Pair,vector<Pair>,greater<Pair> > heap; memset(dis,0x3f,sizeof(dis)); memset(visit,false,sizeof(visit)); heap.push(make_pair(0,s)); dis[s]=0; while(!heap.empty()) { int now=heap.top().second; heap.pop(); if(visit[now]) continue; visit[now]=true; for(int u=first[now];u;u=edge[u].next) { int v=edge[u].to; if(dis[now]+edge[u].val<dis[v]) { dis[v]=dis[now]+edge[u].val; heap.push(make_pair(dis[v],v)); } } } } int in[N]; void dfs1(int now) { visit[now]=true; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(dis[vis]==dis[now]+edge[u].val) //说明在最短路上 { in[vis]++; if(visit[vis]) continue; dfs1(vis); } } } void dfs2(int now) { for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(dis[vis]==dis[now]+edge[u].val) { onroad[u]=true; a[vis]=(a[vis]+a[now])%mod; in[vis]--; if(in[vis]==0) dfs2(vis); } } } void dfs3(int now) { b[now]=1; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(dis[now]+edge[u].val==dis[vis]) { if(!b[vis]) dfs3(vis); //最短路没有环 放心dfs b[now]=(b[now]+b[vis])%mod; } } } void Init() { memset(onroad,false,sizeof(onroad)); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(in,0,sizeof(in)); } int main() { read(n),read(m); for(int i=1,x,y,z;i<=m;i++) { read(x),read(y),read(z); addedge(x,y,z); } for(int i=1;i<=n;i++) { Init(); Dijkstra(i); memset(visit,0,sizeof(visit)); dfs1(i); //来自最短路上的入度 a[i]=1; dfs2(i); //i到每个点最短路的方案数 dfs3(i); //i制造的最短路经过每个点的数量 for(int j=1;j<=m;j++) if(onroad[j]) ans[j]=(ans[j]+a[edge[j].from]*b[edge[j].to]%mod)%mod; } for(int i=1;i<=m;i++) cout<<ans[i]<<'\n'; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/p/9889833.html
