-->http://www.lydsy.com/JudgeOnline/problem.php?id=2750
不说什么了,n遍spfa然后Dp
#include<cstring> #include<cstdio> #include<algorithm> #include<queue> using namespace std; #define nc() getchar() inline int read(){ int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc()); for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x; } #define N 1550 #define ll long long int i,j,k,m,n,x,y,cnt,last[N],dis[N],d[N],a[N],b[N];ll ans[50050]; struct edge{int from,to,next,v;}e[50050];bool vis[N]; inline void add(int w,int v,int u){e[++cnt]=(edge){u,v,last[u],w},last[u]=cnt;} #define met(x,y) memset(x,y,sizeof x) inline void spfa(int s){ queue<int>q;met(dis,0x3f),met(vis,0),dis[s]=0,q.push(s); while(!q.empty()){ int k=q.front();q.pop(),vis[k]=1; for(int i=last[k],y;i;i=e[i].next)if(dis[y=e[i].to]>dis[k]+e[i].v){ dis[y]=dis[k]+e[i].v; if(!vis[y])vis[y]=1,q.push(y); }vis[k]=0; } } #define mo 1000000007 inline void ad(int&a,int b){a+=b;if(a>=mo)a-=mo;} inline void ad(ll&a,ll b){a+=b;if(a>=mo)a-=mo;} void dfs1(int x){vis[x]=1;for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]==dis[x]+e[i].v){++d[y];if(!vis[y])dfs1(y);}} void dfs2(int x){for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]==dis[x]+e[i].v){ad(a[y],a[x]);if(!(--d[y]))dfs2(y);}} void dfs3(int x){b[x]=1;for(int i=last[x],y;i;i=e[i].next)if(dis[y=e[i].to]==dis[x]+e[i].v){if(!b[y])dfs3(y);ad(b[x],b[y]);}} int main(){ for(n=read(),m=read(),i=1;i<=m;++i)add(read(),read(),read()); for(i=1;i<=n;++i){ spfa(i),met(vis,0),met(a,0),met(b,0),met(d,0); dfs1(i),a[i]=1,dfs2(i),dfs3(i); for(j=1;j<=m;++j)if(dis[e[j].from]+e[j].v==dis[e[j].to])ad(ans[j],1ll*a[e[j].from]*b[e[j].to]); } for(i=1;i<=m;++i)printf("%lld\n",ans[i]); }