D - 逃走経路 (Escape Route) 解説 /

実行時間制限: 9 sec / メモリ制限: 2048 MiB

Submission on AtCoder

On AtCoder, use standard input and output. Implement a main function instead of calculate_necessary_time, using the format described under “Input for the Grader” and “Output of the Grader” in the statement.

Input format:

N M S Q
A_0 B_0 L_0 C_0
\vdots
A_{M - 1} B_{M - 1} L_{M - 1} C_{M - 1}
U_0 V_0 T_0
\vdots
U_{Q - 1} V_{Q - 1} T_{Q - 1}

Print Q lines. Line k+1 (0 \le k \le Q - 1) must contain answer[k].

Distributed files

Score: 100 points

Problem Statement

In IOI Kingdom, they use Byou as the unit of time. A day in IOI Kingdom is divided into S units of time. The moment x Byous (0 \le x < S ) after the beginning of a day is called time x. The IOI Kingdom consists of N cities, numbered from 0 to N - 1. There are M roads connecting cities, numbered from 0 to M - 1. You can travel from any city to any other city by passing through some of the roads. The road i (0 \le i \le M - 1) connects the city A_{i} and the city B_{i} bidirectionally. It takes L_{i} Byous to pass through the road i from an endpoint to the other endpoint. Every day, a strict security inspection is performed on the road i from time C_{i} to the end of the day.

JOI Group is one of the secret sects in IOI Kingdom. Since it is a secret sect, the members of JOI Group is strictly confidential. This means members of JOI Group should not encounter a strict security inspection performed every day. Therefore, if a member of JOI Group wants to pass through the road i, the member should depart from either the city A_{i} or the city B_{i} at time x and arrive at the other city at time x + L_{i} for some 0 \le x \le C_{i} - L_{i}. Since a strict security inspection is not performed in the cities, a member of JOI Group may be at in either the city A_{i} or the city B_{i} when a strict security inspection is performed on the road i.

There are Q members in JOI Group, numbered from 0 to Q - 1. The member j (0 \le j \le Q - 1) departs from the city U_{j} at time T_{j} on some day and starts traveling to the city V_{j}. Members are allowed to stay in cities on the way for a while. It may take multiple days for the member j to arrive at the city V_{j}.

Write a program which, given the information of the cities and the roads of IOI Kingdom, the information of strict security inspections, and the information of the members of JOI Group, calculates for each j (0 \le j \le Q - 1) the minimum amount of time required for the member j to travel from the city U_{j} to the city V_{j}.

Implementation Details

In order to speed up input and output, this task is graded with grader.

You need to submit one file. The name of the file you submit is escape_route.cpp. It should implement the following function. The program should include escape_route.h using the preprocessing directive #include.

  • std::vector<long long> calculate_necessary_time( int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B, std::vector<long long> L, std::vector<long long> C, std::vector<int> U, std::vector<int> V, std::vector<long long> T) This function is called exactly once for each test case.
    • The parameter N is the number of cities in IOI Kingdom.
    • The parameter M is the number of roads in IOI Kingdom.
    • The parameter S means a day in IOI Kingdom is S Byous.
    • The parameter Q is the number of members of JOI Group.
    • The parameters A,B,L,C are arrays of length M. They mean the road i (0 \le i \le M - 1) connects the city A[i] and the city B[i], it takes L[i] Byous to pass through the road i, and a strict security inspection on the road i starts at time C[i].
    • The parameters U,V,T are arrays of length Q. They mean the member j (0 \le j \le Q - 1) departs from the city U[j] at time T[j] and starts traveling to the city V[j].
    • This function should return an array answer of long long type and of length Q. It means, for each 0 \le j \le Q - 1, the minimum amount of time required for the member j to travel from the city U[j] to the city V[j] is answer[j] Byous.

Important Notices

  • Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.
  • The grader does not check the format of input. If the format of input is incorrect, the behavior of the grader is not guaranteed.
  • If the length of the array returned by calculate_necessary_time is different from Q or the array contains negative integers, the behavior of the grader is not guaranteed.

Compilation and Test Run

You can download an archive file from the contest webpage which contains the grader to test your program. The archive file also contains a sample source file of your program.

The grader is the file grader.cpp. In order to test your program, put grader.cpp,escape_route.cpp, escape_route.h in the same directory, and run the following command to compile your programs.

g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp escape_route.cpp

When the compilation succeeds, the executable file grader is generated.

In this task, the grader available from the contest webpage is the same as the actual grader used for grading in CMS.

Input for the Grader

The grader reads the following data from the standard input. Given values are all integers.

N M S Q
A_{0} B_{0} L_{0} C_{0}
\vdots
A_{M - 1} B_{M - 1} L_{M - 1} C_{M - 1}
U_{0} V_{0} T_{0}
\vdots
U_{Q - 1} V_{Q - 1} T_{Q - 1}

Output of the Grader

The grader outputs Q lines to the standard output. The (k + 1)-th line (0 \le k \le Q - 1) of output contains answer[k].

Constraints

  • 2 \le N \le 90.
  • N - 1\le M\le\dfrac{N(N - 1)}{2}.
  • 2 \le S \le 1\,000\,000\,000\,000\,000 = 10^{15}.
  • 1 \le Q \le 3\,000\,000.
  • 0 \le A_{i} \le N - 1 (0 \le i \le M - 1).
  • 0 \le B_{i} \le N - 1 (0 \le i \le M - 1).
  • A_{i} \ne B_{i} (0 \le i \le M - 1).
  • (A_{i}, B_{i}) \ne (A_{k}, B_{k}), (A_{i}, B_{i}) \ne (B_{k}, A_{k}) (0 \le i < k \le M - 1).
  • 1 \le L_{i} < S (0 \le i \le M - 1).
  • L_{i} \le C_{i} < S (0 \le i \le M - 1).
  • You can travel from any city to any other city by passing through some of the roads.
  • 0 \le U_{j} \le N - 1 (0 \le j \le Q - 1).
  • 0 \le V_{j} \le N - 1 (0 \le j \le Q - 1).
  • U_{j} \ne V_{j} (0 \le j \le Q - 1).
  • 0 \le T_{j} < S (0 \le j \le Q - 1).

Subtasks

  1. (5 points) N \le 40, Q \le 1\,000,
  2. (20 points) N \le 40, U_{j} = 0 (0 \le j \le Q - 1).
  3. (10 points) N \le 40.
  4. (35 points) N \le 60.
  5. (30 points) No additional constraints.

Sample Input and Output

Sample Input 1

4 5 20 6
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 5
0 3 7
0 3 9
2 0 6
3 1 10
1 2 15

Sample Output 1

3
8
14
2
5
7

This sample input satisfies the constraints of Subtasks 1, 3, 4, 5.

At time 5, the member 0 starts traveling from the city 0 to the city 3. If the member 0 travels in the following way, it takes 3 Byous.

  • Using the road 1, the member 0 departs from the city 0 at time 5, and arrives at the city 2 at time 7.
  • Using the road 4, the member 0 departs from the city 2 at time 7, and arrives at the city 3 at time 8.

Since this is the minimum value, we have \texttt{answer}[0] = 3.

At time 7, the member 1 starts traveling from the city 0 to the city 3. If the member 1 travels in the following way, it takes 8 Byous.

  • Using the road 0, the member 1 departs from the city 0 at time 7, and arrives at the city 1 at time 10.
  • Using the road 2, the member 1 departs from the city 1 at time 10, and arrives at the city 2 at time 14.
  • Using the road 4, the member 1 departs from the city 2 at time 14, and arrives at the city 3 at time 15.

Since this is the minimum value, we have \texttt{answer}[1] = 8.

At time 9, the member 2 starts traveling from the city 0 to the city 3. If the member 2 travels in the following way, the member 2 arrives at the city 3 at time 3 on the next day. In total, it takes 14 Byous.

  • The member 2 stays in the city 0 until time 0 on the next day.
  • Using the road 1, the member 2 departs from the city 0 at time 0, and arrives at the city 2 at time 2.
  • Using the road 4, the member 2 departs from the city 2 at time 2, and arrives at the city 3 at time 3.

Since this is the minimum value, we have \texttt{answer}[2] = 14.

Sample Input 2

6 10 100 9
5 3 4 29
1 0 6 26
0 4 2 7
0 5 18 18
2 0 79 82
3 4 35 46
1 2 15 57
2 4 3 6
4 1 21 83
3 2 47 53
0 2 63
0 4 70
0 4 98
0 5 25
0 5 19
0 4 96
0 5 2
0 3 62
0 3 83

Sample Output 2

42
32
4
93
99
6
102
60
39

This sample input satisfies the constraints of all Subtasks.

Sample Input 3

8 12 1000000000000000 13
2 0 4451698272827 120985696255786
6 5 78520421713825 342652131468508
2 1 185377268405175 382583457603811
0 4 54350742205838 133614919589507
7 0 68486247989149 651590905094148
0 6 85177550834829 299184420663240
5 2 442329739732459 926608308293721
3 7 78020232822359 913548478810253
1 3 267796317244889 687571310475622
5 4 90590208828121 910324397566584
5 7 8414633059584 17796117322043
4 6 45682367792138 204548471584556
7 2 44779065000162
3 5 79376234836942
4 7 305556687070759
4 3 927935834343174
5 1 663284649258985
2 5 967584209777344
5 2 963749709374595
7 4 484562389171308
1 5 446160773830045
6 4 801452311055604
3 1 744524289545354
0 6 467418420721777
5 6 371181379240653

Sample Output 3

72937946261976
929038398222642
702857945988825
272921388674172
580895059624855
181808439529442
117602869946965
569788353034530
1181546234307589
244230056736534
513790925121797
617759130113052
674500988551485

This sample input satisfies the constraints of Subtasks 1, 3, 4, 5.

AtCoder での提出方法

AtCoder では標準入出力を使用してください.calculate_necessary_time の代わりに main 関数を実装し,問題文の「採点プログラムのサンプルの入力・出力」と同じ形式で入出力してください.

入力形式:

N M S Q
A_0 B_0 L_0 C_0
\vdots
A_{M - 1} B_{M - 1} L_{M - 1} C_{M - 1}
U_0 V_0 T_0
\vdots
U_{Q - 1} V_{Q - 1} T_{Q - 1}

Q 行出力し,k+1 行目 (0 \leqq k \leqq Q - 1) に answer[k] を出力してください.

配布ファイル

配点 : 100 点

問題文

IOI 国の 1 日は S 個の単位時間に分割されており,単位としてビョウを用いている .1 日の始まりから x ビョウ (0 \leqq x < S) 経過した時点を時刻 x とする.IOI 国は N 個の都市からなり,0 から N - 1 までの番号が付けられている.また,都市と都市を結ぶ道は M 本あり,0 から M - 1 までの番号が付けられている.どの都市からどの都市へも何本かの道を通ることによって移動することができる.道 i (0 \leqq i \leqq M - 1) は都市 A_{i} と都市 B_{i} を双方向に結んでおり,ちょうど L_{i} ビョウかけて通行することができる.また,毎日時刻 C_{i} からその日が終わるまで道 i 全体で一斉検問が行われている.

秘密結社 JOI 団は IOI 国で暗躍する組織の 1 つである.秘密結社という組織の性質上,構成員は表の人間に知られるわけにはいかない.これは,IOI 国において毎日行われている一斉検問に,構成員が遭遇してはならないということを意味する.したがって,JOI 団の構成員が道 i を通行するには,0 \leqq x \leqq C_{i} - L_{i} を満たす時刻 x に都市 A_{i} と都市 B_{i} のいずれかから出発し,時刻 x + L_{i} にもう一方の都市に到着する必要がある.検問は都市では行われないので,道 i の一斉検問が行われている最中に,都市 A_{i} や都市 B_{i} に構成員がいてもよい.

JOI 団の構成員は Q 人おり,0 から Q - 1 までの番号が付けられている.構成員 j (0 \leqq j \leqq Q - 1) はある日の時刻 T_{j} に都市 U_{j} を出発し,都市 V_{j} を目指して移動を開始する.構成員は移動の最中に都市で待機することもできる.都市 V_{j} にたどり着くまでに複数日かかるかもしれない.

IOI 国の都市と道の情報,一斉検問の情報,JOI 団の構成員の情報が与えられたとき,それぞれの j (0 \leqq j \leqq Q - 1) について,構成員 j が都市 U_{j} を出発してから都市 V_{j} にたどり着くまでにかかる時間の最小値を求めよ.

実装の詳細

この課題の採点は,入出力の高速化のため採点プログラム grader を用いて行う.

あなたは 1 つのファイルを提出しなければならない.ファイルは escape_route.cpp という名前である.このファイルは以下の関数を実装していなければならない.また,#include プリプロセッサ指令によって escape_route.h を読み込むこと.

  • std::vector<long long> calculate_necessary_time( int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B, std::vector<long long> L, std::vector<long long> C, std::vector<int> U, std::vector<int> V, std::vector<long long> T) この関数は,各テストケースにつき 1 回だけ呼び出される.
    • 引数 N は,IOI 国の都市の個数である.
    • 引数 M は,IOI 国の道の本数である.
    • 引数 S は,IOI 国の 1 日が S ビョウであることを表す.
    • 引数 Q は,JOI 団の構成員の人数である.
    • 引数 A,B,L,C は長さ M の配列であり,道 i は都市 A[i] と都市 B[i] を結び,ちょうど L[i] ビョウかけて通行することができ,時刻 C[i] から一斉検問が始まることを表す (0 \leqq i \leqq M - 1).
    • 引数 U,V,T は長さ Q の配列であり,構成員 j は時刻 T[j] に都市 U[j] を出発し,都市 V[j] を目指して移動を開始することを表す (0 \leqq j \leqq Q - 1).
    • この関数は長さ Q の long long 型の配列 answer を返さなければならない.すべての 0 \leqq j \leqq Q - 1 に対して,構成員 j が都市 U[j] を出発してから都市 V[j] にたどり着くまでにかかる時間の最小値は answer[j] ビョウであることを表す.

重要な注意

  • あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.
  • 採点プログラムは入力の形式のチェックを行わない.形式の異なる入力を与えた場合の動作は保証されない.
  • calculate_necessary_time が返す配列の長さが Q でなかったり,配列の要素に負の数が含まれている場合は,採点プログラムの動作は保証されない.

コンパイル・実行の方法

作成したプログラムをテストするための,採点プログラムが,コンテストサイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.

採点プログラムは 1 つのファイルからなる.そのファイルは grader.cpp である.作成したプログラムをテストするには,grader.cpp,escape_route.cpp,escape_route.h を同じディレクトリに置き,次のようにコマンドを実行する.

g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp escape_route.cpp

コンパイルが成功すれば,grader という実行ファイルが生成される.

この課題においては,配布される採点プログラムと CMS での評価に使われる採点プログラムは同一である.

採点プログラムの入力

採点プログラムは標準入力から以下の形式で入力を読み込む.入力はすべて整数でなければならない.

N M S Q
A_{0} B_{0} L_{0} C_{0}
\vdots
A_{M - 1} B_{M - 1} L_{M - 1} C_{M - 1}
U_{0} V_{0} T_{0}
\vdots
U_{Q - 1} V_{Q - 1} T_{Q - 1}

採点プログラムの出力

採点プログラムは標準出力に Q 行出力をする .k + 1 行目 (0 \leqq k \leqq Q - 1) には,answer[k] を出力する.

制約

  • 2 \leqq N \leqq 90.
  • N - 1\leqq M\leqq\dfrac{N(N - 1)}{2}.
  • 2 \leqq S \leqq 1\,000\,000\,000\,000\,000 = 10^{15}.
  • 1 \leqq Q \leqq 3\,000\,000.
  • 0 \leqq A_{i} \leqq N - 1 (0 \leqq i \leqq M - 1).
  • 0 \leqq B_{i} \leqq N - 1 (0 \leqq i \leqq M - 1).
  • A_{i} \ne B_{i} (0 \leqq i \leqq M - 1).
  • (A_{i}, B_{i}) \ne (A_{k}, B_{k}),(A_{i}, B_{i}) \ne (B_{k}, A_{k}) (0 \leqq i < k \leqq M - 1).
  • 1 \leqq L_{i} < S (0 \leqq i \leqq M - 1).
  • L_{i} \leqq C_{i} < S (0 \leqq i \leqq M - 1).
  • どの 2 つの都市の間も,いくつかの道を通ることで行き来可能である.
  • 0 \leqq U_{j} \leqq N - 1 (0 \leqq j \leqq Q - 1).
  • 0 \leqq V_{j} \leqq N - 1 (0 \leqq j \leqq Q - 1).
  • U_{j} \ne V_{j} (0 \leqq j \leqq Q - 1).
  • 0 \leqq T_{j} < S (0 \leqq j \leqq Q - 1).

小課題

  1. (5 点) N \leqq 40,Q \leqq 1\,000.
  2. (20 点) N \leqq 40,U_{j} = 0 (0 \leqq j \leqq Q - 1).
  3. (10 点) N \leqq 40.
  4. (35 点) N \leqq 60.
  5. (30 点) 追加の制約はない.

入出力例

入力例 1

4 5 20 6
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 5
0 3 7
0 3 9
2 0 6
3 1 10
1 2 15

出力例 1

3
8
14
2
5
7

この入力例は小課題 1, 3, 4, 5 の制約を満たす.

構成員 0 は時刻 5 に都市 0 を出発し,都市 3 に移動する.以下のように移動すると 3 ビョウかかる.

  • 道 1 を使用し,時刻 5 に都市 0 を出発して,時刻 7 に都市 2 に到着する.
  • 道 4 を使用し,時刻 7 に都市 2 を出発して,時刻 8 に都市 3 に到着する.

これが最小値なので,\texttt{answer}[0] = 3 である.

構成員 1 は時刻 7 に都市 0 を出発し,都市 3 に移動する.以下のように移動すると 8 ビョウかかる.

  • 道 0 を使用し,時刻 7 に都市 0 を出発して,時刻 10 に都市 1 に到着する.
  • 道 2 を使用し,時刻 10 に都市 1 を出発して,時刻 14 に都市 2 に到着する.
  • 道 4 を使用し,時刻 14 に都市 2 を出発して,時刻 15 に都市 3 に到着する.

これが最小値なので,\texttt{answer}[1] = 8 である.

構成員 2 は時刻 9 に都市 0 を出発し,都市 3 に移動する.以下のように移動すると,翌日の時刻 3 に都市 3 に到着する.合計 14 ビョウかかる.

  • 翌日の時刻 0 まで都市 0 で待機する.
  • 道 1 を使用し,時刻 0 に都市 0 を出発して,時刻 2 に都市 2 に到着する.
  • 道 4 を使用し,時刻 2 に都市 2 を出発して,時刻 3 に都市 3 に到着する.

これが最小値なので,\texttt{answer}[2] = 14 である.

入力例 2

6 10 100 9
5 3 4 29
1 0 6 26
0 4 2 7
0 5 18 18
2 0 79 82
3 4 35 46
1 2 15 57
2 4 3 6
4 1 21 83
3 2 47 53
0 2 63
0 4 70
0 4 98
0 5 25
0 5 19
0 4 96
0 5 2
0 3 62
0 3 83

出力例 2

42
32
4
93
99
6
102
60
39

この入力例はすべての小課題の制約を満たす.

入力例 3

8 12 1000000000000000 13
2 0 4451698272827 120985696255786
6 5 78520421713825 342652131468508
2 1 185377268405175 382583457603811
0 4 54350742205838 133614919589507
7 0 68486247989149 651590905094148
0 6 85177550834829 299184420663240
5 2 442329739732459 926608308293721
3 7 78020232822359 913548478810253
1 3 267796317244889 687571310475622
5 4 90590208828121 910324397566584
5 7 8414633059584 17796117322043
4 6 45682367792138 204548471584556
7 2 44779065000162
3 5 79376234836942
4 7 305556687070759
4 3 927935834343174
5 1 663284649258985
2 5 967584209777344
5 2 963749709374595
7 4 484562389171308
1 5 446160773830045
6 4 801452311055604
3 1 744524289545354
0 6 467418420721777
5 6 371181379240653

出力例 3

72937946261976
929038398222642
702857945988825
272921388674172
580895059624855
181808439529442
117602869946965
569788353034530
1181546234307589
244230056736534
513790925121797
617759130113052
674500988551485

この入力例は小課題 1, 3, 4, 5 の制約を満たす.


出典

JOI 2020/2021 春合宿 Contest Day2 問題1