bzoj2750最短路计数

全栈程序员-站长 • 2021年5月26日下午3:00 • 未分类 • 阅读 95

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2750

枚举每一个起点，通过该边的子树中有多少节点就知道本次它被经过几次了；

　　因为同一起点到该边的起点的最短路唯一。

但其实不是！就在于可以有长度相等的最短路！

所以暴力通过dis[cur]+edge[ i ].w==dis[ v ]?来判断该边是否在当前最短路中。

记录从根到该边起点有多少路径时要保证指向它的点都已赋过值，所以拓扑一下。

别忘了到处写上那个暴力判断！

关于rd，别忘了赋初值。只要每次赋rd[cur]=0就行了。其它会在更新dis时赋好。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int N=1505,M=5005,mod=1e9+7;
int n,m,head[N],pre[N],dis[N],xnt,rd[N];
ll d1[N],d2[N],ans[M];
bool in[N];
queue<int> r;
struct Edge{
    int next,from,to,w;
    Edge(int n=0,int f=0,int t=0,int w=0):next(n),from(f),to(t),w(w) {}
}edge[M];
void spfa(int cur)
{
    memset(dis,1,sizeof dis);
    queue<int> q;
    dis[cur]=0;q.push(cur);in[cur]=1;rd[cur]=0;//
    while(q.size())
    {
        int k=q.front();q.pop();in[k]=0;
        for(int i=head[k],v;i;i=edge[i].next)
        {
            if(dis[k]+edge[i].w==dis[v=edge[i].to])rd[v]++;
            if(dis[k]+edge[i].w<dis[v=edge[i].to])
            {
                rd[v]=1;
                dis[v]=dis[k]+edge[i].w;
                if(!in[v])q.push(v),in[v]=1;
            }
        }
    }
}
void dp(int cur)
{
    d2[cur]=1;
    for(int i=head[cur],v;i;i=edge[i].next)
        if(dis[v=edge[i].to]==dis[cur]+edge[i].w)
        {
            if(!d2[v=edge[i].to])dp(v);
            (d2[cur]+=d2[v])%=mod;
        }
}
void tp(int cur)
{
    r.push(cur);
    for(int i=head[cur],v;i;i=edge[i].next)
        if(dis[v=edge[i].to]==dis[cur]+edge[i].w)//
        {
            rd[v=edge[i].to]--;
            if(!rd[v])tp(v);
        }
}
void solve(int cur)
{
//    printf("cur=%d\n",cur);
    memset(d1,0,sizeof d1);
    memset(d2,0,sizeof d2);
    while(r.size())r.pop();
    spfa(cur);
    tp(cur);
    dp(cur);
    d1[cur]=1;
    while(r.size())
    {
        int k=r.front();r.pop();
        for(int i=head[k],v;i;i=edge[i].next)
            if(dis[v=edge[i].to]==dis[k]+edge[i].w)
                (d1[v]+=d1[k])%=mod;
    }
    for(int i=1,u,v;i<=m;i++)
        if(dis[u=edge[i].from]+edge[i].w==dis[v=edge[i].to])//
        {
            (ans[i]+=d1[u]*d2[v])%=mod;
//            printf("from=%d to=%d t=%lld ans=%lld\n",edge[i].from,edge[i].to,d2[edge[i].to],ans[i]);
        }
}
int main()
{
    scanf("%d%d",&n,&m);int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        edge[++xnt]=Edge(head[x],x,y,z);head[x]=xnt;
    }
    for(int i=1;i<=n;i++)
        solve(i);
    for(int i=1;i<=m;i++)
        printf("%lld\n",ans[i]);
    return 0;
}