bzoj2750最短路计数

bzoj2750最短路计数

题目: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;
}

 

转载于:https://www.cnblogs.com/Narh/p/8870576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101716.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • qt没有被正确安装_qt软件安装步骤

    qt没有被正确安装_qt软件安装步骤对于太长不看的朋友,可参考Qt的安装和使用中的常见问题(简略版)。目录1、概述2、Qt简介3、Qt版本3.1查看安装的Qt版本3.2查看当前项目使用的Qt版本3.3查看当前项目使用

  • activiti 任务节点 处理人设置

    activiti 任务节点 处理人设置1.1.1.前言我们在使用activiti工作流引擎的时候,最常用的肯定是任务节点,因为在OA系统、审批系统、办公自动化系统中核心的处理就是流程的运转,流程的运转依赖于人员如何设置,人员的设置是非常重要的一个环节,所以说如果能让activiti工作流引擎运转的核心,就必须要支持强大的人员组织架构设计。下面我们先说一下activiti工作流引擎自身支持的可以直接使用的地方。我…

  • 机器学习的分类与主要算法对比[通俗易懂]

    机器学习的分类与主要算法对比[通俗易懂]机器学习的分类与主要算法对比重要引用:AndrewNgCoureraMachineLearning;从机器学习谈起;关于机器学习的讨论;机器学习常见算法分类汇总;LeNetHomepage;pluskidsvm  首先让我们瞻仰一下当今机器学习领域的执牛耳者:  这幅图上的三人是当今机器学习界的执牛耳者。中间的是GeoffreyHinton,加拿大多伦多大学的教授,如今被聘为“Goo

  • java使用httpclient调用第三方接口

    java使用httpclient调用第三方接口java使用httpclient调用第三方接口HttpClientUtil工具类packagecom.fz.util;importjava.io.File;importjava.net.URL;importjava.util.ArrayList;importjava.util.List;importjava.util.Map;importorg.apache.ht…

  • VLAN技术_vlan的基本概念、作用和实现原理

    VLAN技术_vlan的基本概念、作用和实现原理本文首次发布于MlinBlog、简书、CSDN,作者@木林(Mlin),转载请保留原文链接。前言正文一、VLAN基本概念1VLAN概述2VLAN帧格式3VLAN链路类型4PVID5VLAN端口类型5.1Access端口5.2Trunk端口5.3Hybrid端口6VLAN划分6.1VLAN划分方法6.2VLAN划分匹配优先级…

  • export命令[通俗易懂]

    export命令[通俗易懂]export命令用于将shell变量输出为环境变量,或者将shell函数输出为环境变量。一个变量创建时,它不会自动地为在它之后创建的shell进程所知。而命令export可以向后面的shell传递变量的值。当一个shell脚本调用并执行时,它不会自动得到原为脚本(调用者)里定义的变量的访问权,除非这些变量已经被显式地设置为可用。export命令可以用于传递一个或多个变量的值到任何后继脚本。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号