题目描述
C国有n座城市，城市之间通过m条[b]单向[/b]道路连接。一条路径被称为最短路，当且仅当不存在从 它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多 少条不同的最短路经过该道路。现在，这个任务交给了你。
输入输出格式
输入格式：
第一行包含两个正整数n、m
接下来m行每行包含三个正整数u、v、w，表示有一条从u到v长度为w的道路
输出格式：
输出应有m行，第i行包含一个数，代表经过第i条道路的最短路的数目对[b]1000000007取模[/b]后的结果
输入输出样例
说明
数据规模
30%的数据满足：n≤15、m≤30
60%的数据满足：n≤300、m≤1000
100%的数据满足：n≤1500、m≤5000、w≤10000
以每一个点为起点，做一次SPFA，把在最短路上的边标记
设S到i的路径数cnt1[i]，在设i到其他点的最短路数cnt2[i]
因为选出来的边构成的图无环，所以用拓扑排序来递推
cnt1[v]+=cnt1[u]
至于cnt2数组，用逆拓扑序递推
于是一条边(u,v)的ans+=cnt1[u]*cnt2[v]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct Node
{
int next,to,dis;
}edge[];
int num,head[],d[];
long long cnt1[],cnt2[],ans[],n,m;
int q[];
bool vis[],pd[];
long long dist[];
int Mod=;
void add(int u,int v,int d)
{
num++;
edge[num].next=head[u];
head[u]=num;
edge[num].to=v;
edge[num].dis=d;
}
void SPFA(int S)
{queue<int>Q;
int i,j;
memset(pd,,sizeof(pd));
memset(vis,,sizeof(vis));
memset(dist,/,sizeof(dist));
memset(d,,sizeof(d));
Q.push(S);
dist[S]=;
while (Q.empty()==)
{
int u=Q.front();
Q.pop();
vis[u]=;
for (i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if (dist[v]>dist[u]+edge[i].dis)
{
dist[v]=dist[u]+edge[i].dis;
if (vis[v]==)
{
vis[v]=;
Q.push(v);
}
}
}
}
for (i=;i<=n;i++)
for (j=head[i];j;j=edge[j].next)
if (dist[i]+edge[j].dis==dist[edge[j].to])
pd[j]=,d[edge[j].to]++;
}
void Top_sort(int S)
{int i,j;
memset(cnt1,,sizeof(cnt1));
memset(cnt2,,sizeof(cnt2));
int h=,t=;
q[]=S;
cnt1[S]=;
while (h<t)
{
h++;
int u=q[h];
for (i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if (pd[i])
{
d[v]--;
cnt1[v]+=cnt1[u];
cnt1[v]%=Mod;
if (d[v]==)
{
t++;
q[t]=v;
}
}
}
}
for (i=t;i>=;i--)
{
int u=q[i];
cnt2[u]++;
for (j=head[u];j;j=edge[j].next)
if (pd[j])
{
int v=edge[j].to;
cnt2[u]+=cnt2[v];
cnt2[u]%=Mod;
}
}
for (i=;i<=n;i++)
for (j=head[i];j;j=edge[j].next)
if (pd[j])
{
int v=edge[j].to;
ans[j]+=cnt1[i]*cnt2[v];
ans[j]%=Mod;
}
}
int main()
{int i,u,v,d;
cin>>n>>m;
for (i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&d);
add(u,v,d);
}
for (i=;i<=n;i++)
{
SPFA(i);
Top_sort(i);
}
for (i=;i<=m;i++)
printf("%lld\n",ans[i]);
}