#P6800. [2019福建夏令营]宝藏

    ID: 6623 传统题 1500ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-图论Floyd–Warshall动态规划子集 DP排序与序列处理前后缀分解CF2600

[2019福建夏令营]宝藏

宝藏(treasure)

题目描述

一座小岛的森林中有 NN 个位置和 MM 条双向小路。第 ii 条小路连接位置 ai,bia_i,b_i,通过它所需的期望步行时间为 cic_i。E.Space 只能沿这些小路步行,不能开辟新的道路。

森林中还有 kk 个结界。第 ii 个结界控制位置 viv_i,使人无法进入或离开这个位置;破解它所需的唯一对应晶石放在位置 ziz_i。E.Space 到达晶石所在的位置后可以取得晶石,并携带它破解对应的结界。他可以同时携带多块晶石。

接下来的 QQ 年,每年 E.Space 都乘直升机来寻找宝藏。第 ii 年,他在位置 sis_i 降落,宝藏位于 tit_i。所有道路、结界、晶石的位置和属性均不改变;每年开始时,结界全部恢复,晶石也全部回到原位。因此,各年的询问互相独立。

请判断每年能否找到宝藏;如果能,求从降落到找到宝藏所需的最少期望步行时间。为取得晶石,可以绕路或重复经过位置和道路。

特别地,如果降落位置被结界控制,就无法降落,该年一定找不到宝藏。

输入格式

第一行三个整数 N,M,kN,M,k。

接下来 MM 行,每行三个正整数 ai,bi,cia_i,b_i,c_i,描述一条双向小路。

接下来 kk 行,每行两个正整数 vi,ziv_i,z_i,描述一个结界及其对应晶石的位置。

接下来一行一个正整数 QQ。

接下来 QQ 行,每行两个正整数 si,tis_i,t_i,描述一年的降落位置与宝藏位置。

输出格式

输出 QQ 行。第 ii 行表示第 ii 年的答案:不能找到宝藏时输出 −1-1,否则输出一个整数,表示最少的期望步行时间。

样例输入

13 15 2
1 2 6
2 3 2
2 4 3
3 4 3
1 5 6
1 6 4
5 7 3
6 7 2
3 8 1
1 9 9
9 10 2
9 11 6
10 12 3
11 12 4
12 13 5
12 7
10 4
4
10 1
5 13
13 12
8 13

样例输出

-1
33
-1
44

样例解释

位置、道路、结界和晶石的分布

图中标出了位置编号和小路的期望步行时间。三角形表示晶石,正方形表示结界,颜色相同表示相互对应。

  • 第一次询问中,位置 1010 有结界,无法降落,答案为 −1-1。
  • 第二次询问中,可以沿 5→7→6→1→9→11→12→135\to7\to6\to1\to9\to11\to12\to13 行走,取得位置 77 的晶石后破解位置 1212 的结界,期望步行时间为 3333。
  • 第三次询问中,无法取得破解位置 1212 的结界所需的晶石,答案为 −1-1。
  • 第四次询问中,可以沿 $8\to3\to4\to2\to1\to6\to7\to6\to1\to9\to10\to12\to13$ 行走,期望步行时间为 4444。

上述两条可行路线分别取得了相应询问的最优值。

数据范围与子任务

所有数据满足 1≤N≤4001\le N\le400,0≤M≤1000000\le M\le100000,0≤k≤160\le k\le16,1≤Q≤2000001\le Q\le200000;所有位置编号均在 11 到 NN 之间,cic_i 为正整数。

子任务 分值 附加限制
1 66 k=0k=0
2 1111 N≤20N\le20,k≤4k\le4
3 1717 N≤50N\le50,k≤7k\le7
4 1818 N≤250N\le250,k≤10k\le10,所有 si=1s_i=1
5 2121 N≤250N\le250,k≤10k\le10
6 1111 k≤14k\le14
7 99 k≤15k\le15
8 77 无