P4102 [HEOI2014]林中路径

    • 24通过
    • 93提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 各省省选 2014 河北
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Alice 和 Marisa 都住在一个巨大的由 N 个路口与 M 条单向小道构成的森林中。Marisa 非常喜欢到 Alice 家里去玩,但是 Alice 并不喜欢这位鲁莽的来客。Alice 非常擅长观察, 因此每当她发现 Marisa 走了一条与之前完全相同的路径来到她家时,她就会装作不在家, Marisa 就只好败兴而归。Marisa 发现了这个秘密,因此她决定每次走不同的路径到 Alice 家。

    Marisa 体力有限,她不想走超过 K 条边到达 Alice 家,并且,每当她走 t(t≤K)条边 到达 Alice 家时,她需要付出 t2的体力。Marisa 想知道,在 Alice 无论如何都不想接见她 之前(即 Marisa 无法走一条长度不超过 K 的与之前不同的路径),她会消耗多少体力。

    现在 Marisa 拿到了一张森林的地图,但因为 Marisa 非常笨,她并不知道自己的家和 Alice 的家在哪一个路口,因此她会给询问你 Q 次,每次询问假如 Marisa 的家的位置在 S 而 Alice 的家的位置在 T 时的答案。

    一条路径 A 的定义是指一个长度为 P(P 可以为任意正整数或零)的边的序列 Am0,Am1,Am2,…,AmT-1,其中对于任意 1≤i<P,有 Ami-1的结束节点是 Ami的起始节点。

    两条路径 A 和 B 完全相同是指两条路径的长度均为 T 并且对任意 0≤i<P,有 Ami=Bmi。

    输入输出格式

    输入格式:

    输入数据第一行包含四个整数 N,M,K,Q,含义如题所述。

    接下来 M 行,每行两个整数 X,Y,表示从第 X 个路口到第 Y 个路口有一条单向小道。路 口的标号为 1,2,3,…,N,在输入数据第 i+1 行的边的标号为 i。 接下来 Q 行,每行两个整数 S 和 T,含义如题所述。

    输出格式:

    对于每个询问,输出一行,表示这次询问的答案。由于 Marisa 接受不了非常大的数, 你只需要输出答案模 1,000,000,007 的值。

    输入输出样例

    输入样例#1: 复制
    2 0 1 1 
    1 2
    输出样例#1: 复制
    0
    输入样例#2: 复制
    2 2 2 1 
    1 2 
    2 1 
    1 1
    输出样例#2: 复制
    4
    输入样例#3: 复制
    2 2 100 1 
    1 2 
    2 1 
    1 2
    输出样例#3: 复制
    166650
    输入样例#4: 复制
    2 3 100 2 
    1 2 
    1 2 
    2 1 
    2 2 
    2 1
    输出样例#4: 复制
    632506153
    51879475

    说明

    对于 20%的数据,N≤5,M≤10,K≤3,Q≤10

    对于 40%的数据,N≤30,M≤900,K≤100,Q≤100

    对于 60%的数据,N≤50,M≤2,500,K≤10,000,000,Q≤1,000

    对于 100%的数据,2≤N≤100,0≤M≤100,000,0≤K≤1,000,000,000,0≤Q≤10,000, 1≤X,Y,S,T≤N

    g++ paths.cpp –o paths –Wl,--stack=268435456 –O2 

    样例一解释 从 S 到 T 不存在路径

    样例二解释 Marisa 可以重复经过一个路口,即使这个路口就是 Alice 的家或 Marisa 的家

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。