Problem : 360 - 1A. 公車路線

Problem Statistics

Solved Member: 14　　Submission: 99　　User Tried: 17

Statement:

你發現在天蓬國搭巴士上課非常的麻煩。

詳細地來說，天蓬國總共有 N 個公車站，由 1 標號到 N。你家住在編號 1 的公車站，你希望達到學校站 N。

天蓬國有 M 班直達公車，每班公車皆行駛其中兩站，在某個時刻發車並在固定時間到達另一站，只要你遲到你整天就再也搭不到這一班車了QAQ。並且你可以經過數次的轉車轉到學校，假設上下車的時間可以忽略，你只要剛好在發車時間或者之前到達發車的公車站就可以搭上該班公車。

你有 Q 天的課表，你知道你每一天必須要在什麼時候之前到達學校的公車站，由於你很懶，你想要計算你最晚什麼時候必須起床到你家旁邊的公車站。

Input:Output:

● 第 1 行有兩個整數 N,M，代表公車站的數量和公車數量。

● 接下來 M 行，每行依序有四個整數 A_i, B_i, X_i, Y_i。代表這一班公車在時間 X_i 從第 A_i 站出發，並在時間 Y_i 到達 B_i 站。

● 下一行有一個整數 Q，代表你有 Q 天的課表想要計算。

● 接下來的 Q 行，每一行有一個整數 L_i，代表你希望在時間 L_i 或之前到達學校的公車站。

限制：
2 ≤ N ≤ 100000
1 ≤ M ≤ 300000
0 ≤ X_i < Y_i < 86400000
1 ≤ A_i, B_i ≤ N, A_i ≠ B_i
1 ≤ Q ≤ 100000
0 ≤ L_i < 86400000

Subtask 1：(20分)
N,M ≤ 2000
Q = 1

Subtask 2：(15分)
N,M ≤ 2000

Subtask 3：(15分)
Q = 1

請輸出 Q 行，每一行輸出一個數字，代表該天最晚要什麼時候到達你家旁邊的公車站。若無法在指定時間之前到達學校車站，請輸出 -1。

Sample Input:Sample Output:

SAMPLE A:
5 6
1 2 10 25
1 2 12 30
2 5 26 50
1 5 5 20
1 4 30 40
4 5 50 70
4
10
30
60
100

SAMPLE B:
3 8
1 2 1 5
1 3 0 1
1 3 2 8
2 3 2 3
2 3 3 4
2 3 4 5
2 3 5 6
2 3 6 7
6
3
4
5
6
7
8

SAMPLE A:
-1
5
10
30

SAMPLE B:
0
0
0
1
1
2

HINT:

SAMPLE A：

詢問1.
無法在時刻 10 之前到學校

詢問2.
時間 5 的時候搭第 4 班公車

詢問3.
時間 10 搭第 1 班公車
時間 25 到站 2，等到時間 26 搭第 3 班公車
時間 50 到站 5

詢問4.
時間 30 搭第 5 班公車
時間 40 到站 4，等到時間 50 搭第 6 班公車
時間 70 到站 5

Source:

2013/2014 JOI 合宿 1模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	500ms	262144kb
0-2	500ms	262144kb
1-1	500ms	262144kb	20
1-2	500ms	262144kb
1-3	500ms	262144kb
1-4	500ms	262144kb
1-5	500ms	262144kb
1-6	500ms	262144kb
1-7	500ms	262144kb
1-8	500ms	262144kb
1-9	500ms	262144kb
1-10	500ms	262144kb
1-11	500ms	262144kb
1-12	500ms	262144kb
1-13	500ms	262144kb
1-14	500ms	262144kb
2-1	500ms	262144kb	15
2-2	500ms	262144kb
2-3	500ms	262144kb
2-4	500ms	262144kb
2-5	500ms	262144kb
2-6	500ms	262144kb
2-7	500ms	262144kb
2-8	500ms	262144kb
2-9	500ms	262144kb
2-10	500ms	262144kb
2-11	500ms	262144kb
2-12	500ms	262144kb
3-1	2000ms	262144kb	15
3-2	2000ms	262144kb
3-3	2000ms	262144kb
3-4	2000ms	262144kb
3-5	2000ms	262144kb
3-6	2000ms	262144kb
3-7	2000ms	262144kb
3-8	2000ms	262144kb
3-9	2000ms	262144kb
3-10	2000ms	262144kb
3-11	2000ms	262144kb
3-12	2000ms	262144kb
3-13	2000ms	262144kb
3-14	2000ms	262144kb
3-15	2000ms	262144kb
3-16	2000ms	262144kb
3-17	2000ms	262144kb
4-1	2000ms	262144kb	50
4-2	2000ms	262144kb
4-3	2000ms	262144kb
4-4	2000ms	262144kb
4-5	2000ms	262144kb
4-6	2000ms	262144kb
4-7	2000ms	262144kb
4-8	2000ms	262144kb
4-9	2000ms	262144kb
4-10	2000ms	262144kb
4-11	2000ms	262144kb
4-12	2000ms	262144kb
4-13	2000ms	262144kb
4-14	2000ms	262144kb
4-15	2000ms	262144kb
4-16	2000ms	262144kb