题意:
给定一张\(n\)个点,\(m\)条边的有向图,求每条边被多少最短路经过
范围&性质:\(1\le n\le 1500,1\le m\le 5000\)
分析:
枚举起点,对于每一个起点,建一颗最短路径树(准确来说是一个DAG),然后枚举边计算贡献,由乘法原理得,一个边会被\(cnt1[frm]\times cnt2[to]\)条路径经过,其中\(cnt1[frm]\)表示起点到这条边的发出点的方案数,\(cnt2[to]\)表示终点到这条边结束点的方案数,方案数可以拓扑排序求得顺序求\(cnt1\),记一下拓扑序后反向求\(cnt2\),总的复杂度为\(O(nmlog_m)\)
代码:
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
using namespace std;
namespace zzc
{
const int mod =1e9+7;
const int maxn = 1e5+5;
int n,m,ecnt=0,gcnt=0;
int head[maxn],siz[maxn];
long long ans[maxn],dis[maxn];
bool ins[maxn],vis[maxn];
struct edge
{
int frm,to,nxt,dis;
}e[maxn];
void add(int u,int v,int w)
{
e[++ecnt].to=v;
e[ecnt].dis=w;
e[ecnt].frm=u;
e[ecnt].nxt=head[u];
head[u]=ecnt;
}
void dijkstra(int st)
{
memset(dis,0x7f,sizeof(dis));
memset(ins,false,sizeof(ins));
memset(vis,false,sizeof(vis));
priority_queue<pii> p;
p.push(mk(0,st));
dis[st]=0;
while(!p.empty())
{
int u=p.top().second;p.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(vis[v]) continue;
if(dis[v]>dis[u]+e[i].dis)
{
dis[v]=dis[u]+e[i].dis;
p.push(mk(-dis[v],v));
}
}
}
for(int i=1;i<=m;i++)
{
if(dis[e[i].frm]+e[i].dis==dis[e[i].to]) ins[i]=true;
}
}
int rd[maxn],cnt1[maxn],cnt2[maxn],num[maxn],tot;
void topo(int st)
{
memset(rd,0,sizeof(rd));
memset(cnt1,0,sizeof(cnt1));
memset(cnt2,0,sizeof(cnt2));
queue<int> q;
q.push(st);
cnt1[st]=1;tot=0;
for(int i=1;i<=m;i++) if(ins[i]) rd[e[i].to]++;
while(!q.empty())
{
int u=q.front();q.pop();
num[++tot]=u;
for(int i=head[u];i;i=e[i].nxt)
{
if(!ins[i]) continue;
int v=e[i].to;
cnt1[v]=(cnt1[v]+cnt1[u])%mod;
if(!(--rd[v])) q.push(v);
}
}
for(int i=tot;i;i--)
{
int u=num[i];
cnt2[u]++;
for(int j=head[u];j;j=e[j].nxt)
{
if(!ins[j]) continue;
int v=e[j].to;
cnt2[u]=(cnt2[u]+cnt2[v])%mod;
}
}
}
void calc(int st)
{
dijkstra(st);
topo(st);
for(int i=1;i<=m;i++)
{
if(!ins[i]) continue;
ans[i]=(ans[i]+1ll*cnt1[e[i].frm]*cnt2[e[i].to]%mod)%mod;
}
}
void work()
{
int a,b,c;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
for(int i=1;i<=n;i++) calc(i);
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}
}
int main()
{
zzc::work();
return 0;
}