#2350. 胖
胖
胖
题目描述
2 胖 2.1 题目描述 Cedyks 是九条可怜的好朋友(可能这场比赛公开以后就不是了),也是这题的主人公。 Cedyks 是一个富有的男孩子。他住在著名的The Place(宫殿)中。 Cedyks 是一个努力的男孩子。他每天都做着不一样的题来锻炼他的The Salt(灵魂)。 这天,他打算在他的宫殿外围修筑一道城墙,城墙上有n 座瞭望塔。你可以把城墙看做一 条线段,瞭望塔是线段上的n 个点,其中1 和n 分别为城墙的两个端点。其中第i 座瞭望塔和 第i + 1 座瞭望塔的距离为wi,他们之间的道路是双向的。 城墙很快就修建好了,现在Cedyks 开始计划修筑他的宫殿到城墙的道路。因为这题的题 目名称,Cedyks 打算用他的宫殿到每一个瞭望塔的最短道路之和来衡量一个修建计划。 现在Cedyks 手上有m 个设计方案,第k 个设计方案会在宫殿和瞭望塔之间修建Tk 条双 向道路,第i 条道路连接着瞭望塔ai,长度为li。 计算到每一个瞭望塔的最短路之和是一个繁重的工程,本来Cedyks 想用广为流传的SPFA 算法来求解,但是因为他的butter(缓冲区)实在是太小了,他只能转而用原始的贝尔福特曼 算法来计算,算法的流程大概如下:
- 定义宫殿是0 号点,第i 个瞭望塔是i 号点,双向边(ui, vi, li) 为一条连接ui 和vi 的双 向道路。令d 为距离数组,最开始d0 = 0, di = 1018(i ∈[1, n])。
- 令辅助数组c = d。依次对于每一条边(ui, vi, wi) 进行增广,cui = min(cui, dvi + wi), cvi = min(cvi, dui + wi)。
- 令t 为c 和d 中不一样的位置个数,即令S = {i|ci̸ = di},则t = |S|。若t = 0,说明d 就是最终的最短路,算法结束。否则令d = c,回到第二步。 因为需要计算的设计方案实在是太多了,所以Cedyks 雇佣了一些人来帮他进行计算。为 了避免这些人用捏造出来的数据偷懒,他定义一个设计方案的校验值为在这个方案上运行贝尔 福特曼算法每一次进入第三步t 的和。他会让好几个雇佣来的人计算同样的设计方案,并比对 每一个人给出的校验值。 你是Cedyks 雇佣来的苦力之一,聪明的你发现在这个情形下计算最短路的长度的和是一 件非常简单的事情。但是寄人篱下不得不低头,你不得不再计算出每一个方案的校验值来交差。 2.2 输入格式 第一行输入两个整数n, m,表示瞭望塔个数和设计方案个数。 接下来一行n −1 个数wi,表示瞭望塔i 和i + 1 之间道路的长度。 接下来m 行,每行描述一个设计方案。第一个整数K 表示设计方案中的道路数量,接下 来K 个数对(ai, li) 为一条宫殿到瞭望塔的边。 4
2.3 输出格式 对于每一个设计方案,输出一行一个整数表示校验值。 2.4 样例输入 5 5 2 3 1 4 1 2 2 2 1 1 4 10 3 1 1 3 1 5 1 3 1 10 2 100 5 1 5 1 1 2 1 3 1 4 1 5 1 2.5 样例输出 5 8 5 8 5 2.6 样例解䞞 • 对于第一个设计方案,每一个阶段d 的变化为: – [0, 1018, 1018, 1018, 1018, 1018] →[0, 1018, 2, 1018, 1018, 1018] → – [0, 4, 2, 5, 1018, 1018] →[0, 4, 2, 5, 6, 1018] →[0, 4, 2, 5, 6, 10]。 因此校验值为1 + 2 + 1 + 1 = 5。 • 对于第二个设计方案,每一个阶段d 的变化为: – [0, 1018, 1018, 1018, 1018, 1018] →[0, 1, 1018, 1018, 10, 1018] → – [0, 1, 3, 11, 10, 14] →[0, 1, 3, 6, 10, 14] →[0, 1, 3, 6, 7, 14] →[0, 1, 3, 6, 7, 11]。 因此校验值为2 + 3 + 1 + 1 + 1 = 8。 • 对于第三个设计方案,每一个阶段d 的变化为: – [0, 1018, 1018, 1018, 1018, 1018] →[0, 1, 1018, 1, 1018, 1] →[0, 1, 3, 1, 2, 1]。 因此校验值为3 + 1 + 1 = 5。 • 对于第四个设计方案,每一个阶段d 的变化为: – [0, 1018, 1018, 1018, 1018, 1018] →[0, 10, 100, 1018, 1018, 1] → – [0, 10, 12, 103, 5, 1] →[0, 10, 12, 6, 5, 1] →[0, 10, 9, 5, 1]。 因此校验值为3 + 3 + 1 + 1 = 8。 5
• 对于第五个设计方案,每一个阶段d 的变化为: – [0, 1018, 1018, 1018, 1018, 1018] →[0, 1, 1, 1, 1, 1] 因此校验值为5。 2.7 数据㣗围与约定 测试点 n m K 其他约定 1 ≤1000 ≤1000 ≤100 无 2 3 ≤2 × 105 ≤2 × 105 4 5 ≤2 × 105 1 ≤wi, li ≤50 6 7 无 8 9 10 对于100% 的数据,保证每个设计方案ai 两两不同且1 ≤ai ≤n。 对于100% 的数据,保证1 ≤wi, li ≤109, 1 ≤∑K ≤2 × 105。 6
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 5
2 3 1 4
1 2 2
2 1 1 4 10
3 1 1 3 1 5 1
3 1 10 2 100 5 1
5 1 1 2 1 3 1 4 1 5 1
5
8
5
8
5