#P13081. [NOISG 2017] Roadside Advertisements / 广告投放

    ID: 12712 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2017NOISG(新加坡)

[NOISG 2017] Roadside Advertisements / 广告投放

题目背景

译自 NOISG 2017 B.Roadside Advertisements


NOISG2017 拥有 55 个赞助商。

题目描述

新加坡的地图可以视为一张 VV 个点 V1V-1 条边的图,其中点的编号为 0,1,V10,1,\cdots V-1。保证任意两点间有且仅有唯一路径。

已知 55 个赞助商分别位于 a,b,c,d,ea,b,c,d,e 号点,NOISG 主席 TAN Sun-Teck 想要在一些边上投放广告,使得 55 个赞助商两两间的最短路径上都投放了至少一则广告。

对于每条边,在该边上投放广告的成本是已知的。投放广告的总成本是每条需投放广告的道路成本的总和。QQ 次询问,每次给定 a,b,c,d,ea,b,c,d,e,求满足要求的最低总成本。

输入格式

第一行一个正整数 VV

接下来 V1V−1 行,每行三个整数 u,v,wu,v,w,表示 uu 号点和 vv 号点间有一条道路相连,并且在这条道路上投放广告需要 ww 新加坡元。

接下来一行包含一个正整数 QQ,表示询问次数。

接下来 QQ 行,每行五个整数 a,b,c,d,ea,b,c,d,e,表示 55 个赞助商的位置。保证 a,b,c,d,ea,b,c,d,e 两两不同。

输出格式

对于每次询问,一行一个整数表示投放广告的最低总成本。

5
0 1 1
1 2 2
2 3 3
3 4 4
1
4 0 3 1 2
10
6
4 0 4
0 1 2
1 3 9
3 5 1
3 2 5
2
4 0 3 5 2
0 4 1 3 5
21
16

提示

【样例 2 解释】

对于第一次询问,55 个赞助商分别位于 4,0,3,5,24,0,3,5,2 号点(请注意编号不一定按升序排列)。易知我们需要在每一条路边投放广告,最低成本是所有道路的成本之和,即 4+2+9+1+5=214+2+9+1+5=21

对于第二次询问,55 个赞助商位于 0,4,1,3,50,4,1,3,5 号点。这一次我们不需要在 (3,2)(3,2) 这条道路上投放广告。因此总成本为 215=1621−5=16

【数据范围】

本题采用 Subtask\text{Subtask} 捆绑测试。

Subtask\text{Subtask} 分值 V,QV,Q 的范围 特殊性质
11 77 V=5,Q=1V=5,Q=1
22 2323 5V5×104,1Q1045\le V\le5\times10^4,1\le Q\le 10^4
33 4040 5V5×104,1Q1005\le V\le5\times10^4,1\le Q\le 100
44 3030 5V5×104,1Q1045\le V\le5\times10^4,1\le Q\le 10^4

特殊性质:保证每个点最多与 22 个点间有道路相连。

对于所有数据,保证 5V5×1045\le V\le5\times10^41Q1041\le Q\le 10^40u,v<V0\le u,v<V1w10001\le w\le1000