OpenJudge

2:观光公交

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
128000kB
描述


输入
第 1 行是 3 个整数 n, m, k,每两个整数之间用一个空格隔开。分别表示景点数、乘客数
和氮气加速器个数。
第 2 行是 n-1 个整数,每两个整数之间用一个空格隔开,第 i 个数表示从第 i 个景点开
往第 i+1 个景点所需要的时间,即 D i 。
第 3 行至 m+2 行每行 3 个整数 T i , A i , B i ,每两个整数之间用一个空格隔开。第 i+2 行表
示第 i 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。
输出
共一行,包含一个整数,表示最小的总旅行时间。
样例输入
3 3 2
1 4
0 1 3
1 1 2
5 2 3
样例输出
10
提示
对于 10%的数据,k=0;
对于 20%的数据,k=1;
对于 40%的数据,2 ≤ n ≤ 50,1 ≤ m ≤ 1,000,0 ≤ k ≤ 20,0 ≤ D i ≤ 10,0 ≤ T i ≤ 500;
对于 60%的数据,1 ≤ n ≤ 100,1 ≤ m ≤ 1,000,0 ≤ k ≤ 100,0 ≤ D i ≤ 100,0 ≤ T i ≤ 10,000;
对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ m ≤ 10,000,0 ≤ k ≤ 100,000,0 ≤ D i ≤ 100,
0 ≤ T i ≤ 100,000。
来源
NOIP2011
全局题号
11196
添加于
2016-08-14
提交次数
4
尝试人数
1
通过人数
1