[HAOI2012]道路(最短路DAG上计数)

时间:2023-01-30 16:44:04

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<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define N 1503
#define M 5002
#define wj 1000000007
#define mm make_pair
#define R register
using 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<int>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=;
char c=getchar();while(!isdigit(c))c=getchar();
while(isdigit(c)){
x=(x<<)+(x<<)+(c^);
c=getchar();
}
return x;
}
int main(){
n=rd();m=rd();
for(int i=;i<=m;++i){
u=rd();v=rd();w=rd();
add(u,v,w);
}
for(R int S=;S<=n;++S){
q.push(S);
memset(dis,0x3f,sizeof(dis));dis[S]=;
memset(vis,,sizeof(vis)); top=;
memset(dp,,sizeof(dp));memset(dp2,,sizeof(dp2));
while(!q.empty()){
R int u=q.front();q.pop();vis[u]=;
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]=;
q.push(v);
}
}
}
}
memset(pd,,sizeof(pd));
for(int u=;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]=;
dp[S]=;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>=;--i){
dp2[st[i]]=;
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=;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=;i<=tot;++i)printf("%d\n",ans[i]);
return ;
}