21787번 - Escape Route 서브태스크다국어언어 제한함수 구현

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 ≤ 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 ≤ i ≤ 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 ≤ x ≤ 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 ≤ j ≤ 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 ≤ j ≤ Q − 1) the minimum amount of time required for the member j to travel from the city U_j to the city V_j.

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 ≤ i ≤ 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 ≤ j ≤ 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 ≤ j ≤ 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.

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

N M S Q
A0 B0 L0 C0
.
.
.
AM−1 BM−1 LM−1 CM−1
U0 V0 T0
.
.
.
UQ−1 VQ−1 TQ−1

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

• 2 ≤ N ≤ 90.
• N − 1 ≤ M ≤ N(N − 1)/2.
• 2 ≤ S ≤ 1 000 000 000 000 000 = 10¹⁵.
• 1 ≤ Q ≤ 3 000 000.
• 0 ≤ A_i ≤ N − 1 (0 ≤ i ≤ M − 1).
• 0 ≤ B_i ≤ N − 1 (0 ≤ i ≤ M − 1).
• A_i ≠ B_i (0 ≤ i ≤ M − 1).
• (A_i, B_i) ≠ (A_k, B_k), (A_i, B_i) ≠ (B_k, A_k) (0 ≤ i < k ≤ M − 1).
• 1 ≤ L_i < S (0 ≤ i ≤ M − 1).
• L_i ≤ C_i < S (0 ≤ i ≤ M − 1).
• You can travel from any city to any other city by passing through some of the roads.
• 0 ≤ U_j ≤ N − 1 (0 ≤ j ≤ Q − 1).
• 0 ≤ V_j ≤ N − 1 (0 ≤ j ≤ Q − 1).
• U_j ≠ V_j (0 ≤ j ≤ Q − 1).
• 0 ≤ T_j < S (0 ≤ j ≤ Q − 1).

• escape_route-dist.zip