问题 25166 --【NOIP2011tg_Day2】观光公交

25166: 【NOIP2011tg_Day2】观光公交

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][764kb]

题目描述

3.观光公交

bus.cpp/c/pas

【问题描述】

风景迷人的小城 Y 市,拥有 n 个美丽的景点。由于慕名而来的游客越来越多,Y 市特 意安排了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1 号景点,随后依次前往 2、3、4……n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。 任意时刻,公交车只能往前开,或在景点处等待。

设共有 m 个游客,每位游客需要乘车 1 次从一个景点到达另一个景点,第 i 位游客在

Ti 分钟来到景点 Ai,希望乘车前往景点 Bi(Ai<Bi)。为了使所有乘客都能顺利到达目的地,公交站都待需景点所有上车出发一景假设乘客上下车不需要时间。

一个乘客的旅行时间,等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司 机 ZZ 给公交车安装了 k 个氮气加速器,每使用一个加速器,可以使其中一个 Di 减 1。对于 同一个 Di 可以重复使用加速器,但是必须保证使用后 Di 大于等于 0

那么 ZZ 该如何安排使用加速器,才能使所有乘客的旅行时间总和最小?

 

【输入】

输入文件名为 bus.in。

第 1 行是 3 个整数 n, m, k,每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

第 2 行是 n-1 个整数,每两个整数之间用一个空格隔开,第 i 个数表示从第 i 个景点开 往第 i+1 个景点所需要的时间,即 Di。

第 3 行至 m+2 行每行 3 个整数 Ti, Ai, Bi,每两个整数之间用一个空格隔开。第 i+2 行表 示第 i 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。

 

【输出】

输出文件名为 bus.out。共一行,包含一个整数,表示最小的总旅行时间。

 

【输入输出样例】

 

bus.in

bus.out

3 3 2

1 4

0 1 3

1 1 2

5 2 3

10


【输入输出样例说明】

对 D2 使用 2 个加速器,从 2 号景点到 3 号景点时间变为 2 分钟。

公交车在第 1 分钟从 1 号景点出发,第 2 分钟到达 2 号景点,第 5 分钟从 2 号景点出发,第 7 分钟到达 3 号景点。

第 1 个旅客旅行时间 7-0 = 7 分钟。 第 2 个旅客旅行时间 2-1 = 1 分钟。 第 3 个旅客旅行时间 7-5 = 2 分钟。 总时间 7+1+2 = 10 分钟。


【数据范围】

对于 10%的数据,k=0; 对于 20%的数据,k=1;

对于 40%的数据,2 ≤ n ≤ 50,1 ≤ m ≤ 1,000,0 ≤ k ≤ 20,0 ≤ Di ≤ 10,0 ≤ Ti ≤ 500;

对于 60%的数据,1 ≤ n ≤ 100,1 ≤ m ≤ 1,000,0 ≤ k ≤ 100,0 ≤ Di ≤ 100,0 ≤ Ti ≤ 10,000;

对于 100% 的数据,1 ≤ n ≤ 1,000 ,1 ≤ m ≤ 10,000 ,0 ≤ k ≤ 100,000 ,0 ≤ Di ≤ 100 ,0 ≤ Ti ≤ 100,000。

输入

输出

提示

来源

[提交][状态]