BZOJ2750: [HAOI2012]Road（洛谷P2505）

最短路 拓撲排序

BZOJ題目傳送門

洛谷題目傳送門

對于每個點跑一遍最短路（Dij很穩，spfa也可以）。一條邊在最短路上當 d [ x ] + d = d [ v ] d[x]+d=d[v] d[x]+d=d[v]。我們對跑出來的圖進行拓撲排序，正着做一遍求出從起點到達點 i i i的最短路方案 s 1 [ i ] s1[i] s1[i]，倒着做一遍求出以點 i i i為起點的最短路方案 s 2 [ i ] s2[i] s2[i]。一條邊在這張圖裡的貢獻就是 s 1 [ x ] ∗ s 2 [ v ] s1[x]*s2[v] s1[x]∗s2[v]。

代碼：

#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1505
#define M 5005
#define F inline
using namespace std;
const long long p=1e9+7;
struct edge{ int nxt,to,d; }ed[M];
int n,m,k,h[N],d[N],q[N],qq[N<<4],s1[N],s2[N],in[N],ans[M];
bool f[N],ff[M];
F char readc(){
	static char buf[100000],*l=buf,*r=buf;
	if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
	return l==r?EOF:*l++;
}
F int _read(){
	int x=0; char ch=readc();
	while (!isdigit(ch)) ch=readc();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
	return x;
}
#define add(x,y,z) ed[++k]=(edge){h[x],y,z},h[x]=k
F void spfa(int s){
	for (int i=1;i<=n;i++) d[i]=1e9,f[i]=false,in[i]=0;
	int l=0,r=1; qq[1]=s,d[s]=0;
	while (l<r){
		int x=qq[++l]; f[x]=false;
		for (int i=h[x],v;i;i=ed[i].nxt)
			if (d[v=ed[i].to]>d[x]+ed[i].d){
				d[v]=d[x]+ed[i].d;
				if (!f[v]) qq[++r]=v,f[v]=true;
			}
	}
}
F void tp(int s){
	for (int i=1;i<=m;i++) ff[i]=false;
	for (int x=1;x<=n;x++)
		for (int i=h[x],v;i;i=ed[i].nxt)
			v=ed[i].to,in[v]+=(ff[i]=(d[x]+ed[i].d==d[v]));
	for (int i=1;i<=n;i++) s1[i]=0,s2[i]=1;
	int l=0,r=1; q[1]=s,s1[s]=1;
	while (l<r)
		for (int x=q[++l],i=h[x],v;i;i=ed[i].nxt)
			if (ff[i]&&!(--in[v=ed[i].to])) q[++r]=v;
	for (int i=1,x=q[i];i<=r;x=q[++i])
		for (int j=h[x];j;j=ed[j].nxt)
			if (ff[j]) s1[ed[j].to]+=s1[x];
	for (int i=r,x=q[i];i;x=q[--i])
		for (int j=h[x];j;j=ed[j].nxt)
			if (ff[j]) s2[x]+=s2[ed[j].to];
	for (int x=1;x<=n;x++)
		for (int i=h[x];i;i=ed[i].nxt)
			if (ff[i]) (ans[i]+=1ll*s1[x]*s2[ed[i].to]%p)%=p;
}
int main(){
	n=_read(),m=_read();
	for (int i=1,x,y,z;i<=m;i++)
		x=_read(),y=_read(),z=_read(),add(x,y,z);
	for (int i=1;i<=n;i++) spfa(i),tp(i);
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}