大作业的复仇 - 题目

内存限制：512 MiB 时间限制：1500 ms 标准输入输出

题目类型：传统评测方式：文本比较

上传者： YangDavid

在一次数据结构课中，你的作业被选为优秀大作业，获得了上台展示的机会。在上台展示开始之前的一个小时，助教David偷偷告诉你，这节课的代课老师Yang教授安排的上台展示内容竟然是在OJ上现场评测你的代码！更可怕的是，你发现这个评测的要求竟然比你写的作业更高。你感到无比恐慌，并要尽快调整你的代码从而通过上台展示，让Yang教授给你这门课的满分。

有个城市与个单向火车车次，第趟火车会于发车时间从起点站出发，在到达时间到达终点站，中间不停车，票价是。要乘坐这列火车，你必须在时刻或时刻之前到达这个车站，然后你就会在时刻出现在车站。由于你是专业卡 deadline 选手，上下车、转车的时间均可以忽略不计，也就是若你在时刻刚刚从某站下车，你仍然可以赶上在这一站时刻出发的列车。

现在是时刻，你正处于车站，你想知道到达各个其他车站的最优方案是什么（你可以转车、在某个车站等待等），可是你需要考虑很多因素：

票价，即方案中乘坐的所有火车的票价之和。
乘车次数，即一共要乘坐几次火车。
旅途总用时，即到达目的地的时刻减去当前的时刻的值。

你想要综合考虑这些因素，因此你选取了三个非负整数，定义方案的“代价”为。你想知道对每个城市，到达这个城市的方案“代价”的最小值是多少。如果无法到达某个城市，请在相应位置输出。

第一行三个正整数表示城市数、火车路线数和你目前所在的城市。（）

第二行三个非负整数，意义如题目描述中所示。（）

接下来行描述火车车次，每行五个整数（），表示路线的起点站城市编号、终点站城市编号、出发时间、到达时间与票价。

共行，第行一个整数表示从城市到城市最优方案的“代价”，如果无法到达城市，则这一行是。

样例输入1

5 7 4
1 0 0
2 3 9 11 1
1 2 0 1 3
5 1 3 5 1
3 4 12 15 1
4 5 0 2 1000
5 3 3 4 1000
1 2 6 8 1

样例输出1

样例输入2

5 7 4
0 1 0
2 3 9 11 1
1 2 0 1 3
5 1 3 5 1
3 4 12 15 1
4 5 0 2 1000
5 3 3 4 1000
1 2 6 8 1

样例输出2

样例输入3

5 7 4
0 0 1
2 3 9 11 1
1 2 0 1 3
5 1 3 5 1
3 4 12 15 1
4 5 0 2 1000
5 3 3 4 1000
1 2 6 8 1

样例输出3

样例输入4

5 7 1
2 3 3
2 3 9 11 1
1 2 0 1 3
5 1 3 5 1
3 4 12 15 1
4 5 0 2 1000
5 3 3 4 1000
1 2 6 8 1

样例输出4

样例解释

以上四个样例对应的都是如下的交通图，只是起点站和优化策略不同。（路线上的 # 后的数字表示边的编号，a:b 表示 a 时刻出发，b 时刻到达，￥后的数字表示票价）

输入较大，请使用较快的输入输出方式（如 scanf，关同步后的 cin 等）。如有需要，下面提供一个快速输入/输出模板供参考。（但此题目时间限制已是没用快速输入输出标程的 3 倍）

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<typename T> void read(T &x){
    x = 0; int f = 1; char ch = gc();
    while(!isdigit(ch) ) { if(ch == '-') f = -1; ch = gc();}
    while( isdigit(ch) ) {x = x * 10 + ch - 48; ch = gc();}
    x *= f;
}
template<typename T, typename... Args> void read(T& x, Args&... args)
{ read(x), read(args...); }
template<typename T> void write(T x) {
    if(x < 0) { putchar('-'), write(-x); return; }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

最好采用线性算法。

编辑器加载中 …

或者，上传代码文件

#1164. 大作业的复仇

题目描述

输入格式

输出格式

样例

数据范围与提示

显示分类标签