#P6800. [2019福建夏令营]宝藏
[2019福建夏令营]宝藏
宝藏(treasure)
题目描述
一座小岛的森林中有 个位置和 条双向小路。第 条小路连接位置 ,通过它所需的期望步行时间为 。E.Space 只能沿这些小路步行,不能开辟新的道路。
森林中还有 个结界。第 个结界控制位置 ,使人无法进入或离开这个位置;破解它所需的唯一对应晶石放在位置 。E.Space 到达晶石所在的位置后可以取得晶石,并携带它破解对应的结界。他可以同时携带多块晶石。
接下来的 年,每年 E.Space 都乘直升机来寻找宝藏。第 年,他在位置 降落,宝藏位于 。所有道路、结界、晶石的位置和属性均不改变;每年开始时,结界全部恢复,晶石也全部回到原位。因此,各年的询问互相独立。
请判断每年能否找到宝藏;如果能,求从降落到找到宝藏所需的最少期望步行时间。为取得晶石,可以绕路或重复经过位置和道路。
特别地,如果降落位置被结界控制,就无法降落,该年一定找不到宝藏。
输入格式
第一行三个整数 。
接下来 行,每行三个正整数 ,描述一条双向小路。
接下来 行,每行两个正整数 ,描述一个结界及其对应晶石的位置。
接下来一行一个正整数 。
接下来 行,每行两个正整数 ,描述一年的降落位置与宝藏位置。
输出格式
输出 行。第 行表示第 年的答案:不能找到宝藏时输出 ,否则输出一个整数,表示最少的期望步行时间。
样例输入
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
样例解释

图中标出了位置编号和小路的期望步行时间。三角形表示晶石,正方形表示结界,颜色相同表示相互对应。
- 第一次询问中,位置 有结界,无法降落,答案为 。
- 第二次询问中,可以沿 行走,取得位置 的晶石后破解位置 的结界,期望步行时间为 。
- 第三次询问中,无法取得破解位置 的结界所需的晶石,答案为 。
- 第四次询问中,可以沿 $8\to3\to4\to2\to1\to6\to7\to6\to1\to9\to10\to12\to13$ 行走,期望步行时间为 。
上述两条可行路线分别取得了相应询问的最优值。
数据范围与子任务
所有数据满足 ,,,;所有位置编号均在 到 之间, 为正整数。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | ||
| 2 | , | |
| 3 | , | |
| 4 | ,,所有 | |
| 5 | , | |
| 6 | ||
| 7 | ||
| 8 | 无 |