C国有n座城市，城市之间通过m条[b]单向[/b]道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。
Solution
我们要求每条边上最短路经过的数量，看上去非常不好求，但注意到点数只有1500，边数只有5000，可以考虑枚举源点，把所有答案加起来就是最后的答案。
问题来了，对于确定的原点，我们怎么计数？
这时我们可以考虑在DAG上弄一弄。
我们将dp[S]=1,只把S加入队列，跑一边拓扑，dp[v]+=dp[u]（这时对于最短路DAG上的）。
在按照拓扑序反着来一遍，dp[u]+=dp[v](初始所有dp[u]=1)。
然后我就在想一个问题，为什么逛公园那题必须把所有入度为0的点加入队列，而这个题只能把S加入队列。
原因是：逛公园那题需要判0环，如果只加入S，会出现BUG，这题要计数，把所有点加进去会多算一些东西。
图论就是这么奇妙23333
Code
#include#include #include #include #define N 1503#define M 5002 #define wj 1000000007#define mm make_pair#define R registerusing namespace std;//对与每个点有多少最短路经过该点。int u,v,w,dis[N],head[N],tot,n,m,du[N],st[N],top,pd[M]; long long dp[N],dp2[N],ans[M];bool vis[N];queue q;struct fe{ int n,to,l;}e[M];inline void add(R int u,R int v,R int l){ e[++tot].n=head[u]; e[tot].to=v; head[u]=tot;e[tot].l=l;}int rd(){ int x=0; char c=getchar();while(!isdigit(c))c=getchar(); while(isdigit(c)){ x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x;}int main(){ n=rd();m=rd(); for(int i=1;i<=m;++i){ u=rd();v=rd();w=rd(); add(u,v,w); } for(R int S=1;S<=n;++S){ q.push(S); memset(dis,0x3f,sizeof(dis));dis[S]=0; memset(vis,0,sizeof(vis)); top=0; memset(dp,0,sizeof(dp));memset(dp2,0,sizeof(dp2)); while(!q.empty()){ R int u=q.front();q.pop();vis[u]=0; for(R int i=head[u];i;i=e[i].n){ R int v=e[i].to; if(dis[v]>dis[u]+e[i].l){ dis[v]=dis[u]+e[i].l; if(!vis[v]){ vis[v]=1; q.push(v); } } } } memset(pd,0,sizeof(pd)); for(int u=1;u<=n;++u) for(int i=head[u];i;i=e[i].n) if(dis[e[i].to]==dis[u]+e[i].l)du[e[i].to]++,pd[i]=1; dp[S]=1;q.push(S); while(!q.empty()){ int u=q.front();q.pop();st[++top]=u; for(R int i=head[u];i;i=e[i].n)if(pd[i]){ if(!--du[e[i].to])q.push(e[i].to);(dp[e[i].to]+=dp[u])%=wj; } } for(R int i=top;i>=1;--i){ dp2[st[i]]=1; for(R int j=head[st[i]];j;j=e[j].n)if(pd[j]) (dp2[st[i]]+=dp2[e[j].to])%=wj; } for(R int u=1;u<=n;++u) for(R int i=head[u];i;i=e[i].n)if(pd[i])(ans[i]+=dp[u]*dp2[e[i].to])%=wj; } for(R int i=1;i<=tot;++i)printf("%d\n",ans[i]); return 0;}