시간 제한메모리 제한제출정답맞힌 사람정답 비율
10 초 256 MB34101034.483%

문제

There are N cities in JOI country, numbered from 0 to N − 1. There are A railway lines, numbered from 0 to A − 1. The railway line i (0 ≤ i ≤ A − 1) connects the city Ui and the city Vi bidirectionally, and its fare is Ci. Different railway lines connect different pairs of cities. There are B bus lines, numbered from 0 to B − 1. The bus line j (0 ≤ j ≤ B − 1) connects the city Sj and the city Tj bidirectionally, and its fare is Dj. Different bus lines connect different pairs of cities, but a railway line and a bus line might connect the same pair of cities. It is possible to travel between any pair of cities by taking railways and/or buses.

Azer wants to know the minimum total fare needed to travel from the city 0 to each city. As Azer knows only about railway lines, he cooperates with Baijan, who knows only about bus lines.

They communicate with each other by sending and receiving characters 0 or 1. The total number of the sent characters should be less than or equal to 58 000.

Write programs which, Azer’s program given the information of railway lines, and Baijan’s given the information of bus lines, communicating with each other, help Azer find the minimum total fare needed to travel from the city 0 to each city.

구현

You need to submit two files.

The name of the first file is Azer.cpp. It represents the behavior of Azer and should implement the following functions. The file should include Azer.h.

  • void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C)
    This function is executed exactly once at the beginning.
    • Parameter N is N, the number of cities.
    • Parameter A is A, the number of railway lines.
    • Parameters U, V are arrays of length A. U[i] and V[i] are Ui and Vi, the cities connected by the railway line i (0 ≤ i ≤ A − 1).
    • Parameter C is an array of length A. C[i] is Ci, the fare of the railway line i (0 ≤ i ≤ A − 1).
  • void ReceiveA(bool x)
    This function is executed every time a character is sent from Baijan.
    • The parameter x represents the character sent from Baijan: true for character 1, and false for character 0.
  • std::vector<int> Answer()
    This function is executed exactly once when all the sent characters have been received. This function must return an array Z containing the minimum total fare needed to travel from the city 0 to each city.
    • The return value Z must be an array of length N. If its length is not N, your program is judged as Wrong Answer [1]. Z[k] (0 ≤ k ≤ N − 1) must be the minimum total fare needed to travel from the city 0 to the city k. In particular, note that Z[0] = 0 must be satisfied.

Your program can call the following function in this file.

  • void SendA(bool y)
    Use this function to send a character to Baijan.
    • The parameter y represents the character to send to Baijan: true for character 1, and false for character 0.

The name of the second file is Baijan.cpp. It represents the behavior of Baijan and should implement the following functions. The file should include Baijan.h.

  • void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D)
    This function is executed exactly once at the beginning.
    • Parameter N is N, the number of cities.
    • Parameter B is B, the number of bus lines.
    • Parameters S, T are arrays of length B. S[j] and T[j] are Sj and Tj, the cities connected by bus line j (0 ≤ j ≤ B − 1).
    • Parameter D is an array of length B. D[j] is Dj, the fare of bus line j (0 ≤ j ≤ B − 1).
  • void ReceiveB(bool y)
    This function is executed every time a character is sent from Azer.
    • The parameter y represents the character sent from Azer: true for character 1, and false for character 0.

Your program can call the following function in this file.

  • void SendB(bool x)
    Use this function to send a character to Azer.
    • The parameter x represents the character to send to Azer: true for character 1, and false for character 0.

You can assume that the program is executed as follows. For each test case, two queues are prepared: QY, where characters Azer sends are stored, and QX, where characters Baijan sends are stored. First, InitA and InitB are executed, and the sent characters are pushed to the corresponding queues.

  • If either QX or QY is not empty, one character is popped from it and corresponding ReceiveA or ReceiveB is executed. However, if both QX and QY are not empty, it is not determined whether ReceiveA or ReceiveB is executed.
  • When SendA is executed during executions of ReceiveA, the sent character is pushed to QY.
  • When SendB is executed during executions of ReceiveB, the sent character is pushed to QX.
  • If both queues are empty, Answer is executed and the program ends.

The total number of characters Azer and Baijan send should be less than or equal to 58 000. If it is larger, your program is judged as Wrong Answer [2].

입력

The sample grader reads the input data from the standard input in the following format.

N A B
U0 V0 C0
.
.
.
UA−1 VA−1 CA−1
S0 T0 D0
.
.
.
SB−1 TB−1 DB−1

출력

The sample grader writes the following information to the standard output and the standard error (quotes for clarity).

  • If your program is judged as Wrong Answer [1] or Wrong Answer [2], it writes its type as “Wrong Answer [1]” to the standard error. It writes nothing to the standard output.
  • Otherwise, it writes the total number of the sent characters L as “Accepted: L” to the standard error. It also writes your answer Z to the standard output as follows:
    Z[0]
    .
    .
    .
    Z[N - 1]
    The sample grader does not check if the value of Z is correct.

If your program is judged as several types of Wrong Answer, the sample grader reports only one of them.

제한

  • 1 ≤ N ≤ 2 000.
  • 0 ≤ A ≤ 500 000.
  • 0 ≤ B ≤ 500 000.
  • 0 ≤ Ui ≤ N − 1 (0 ≤ i ≤ A − 1).
  • 0 ≤ Vi ≤ N − 1 (0 ≤ i ≤ A − 1).
  • Ui ≠ Vi (0 ≤ i ≤ A − 1).
  • (Ui1, Vi1) ≠ (Ui2, Vi2) and (Ui1, Vi1) ≠ (Vi2, Ui2) (0 ≤ i1 < i2 ≤ A − 1).
  • 0 ≤ Sj ≤ N − 1 (0 ≤ j ≤ B − 1).
  • 0 ≤ Tj ≤ N − 1 (0 ≤ j ≤ B − 1).
  • Sj ≠ Tj (0 ≤ j ≤ B − 1).
  • (Sj1, Tj1) ≠ (Sj2, Tj2) and (Sj1, Tj1) ≠ (Tj2, Sj2) (0 ≤ j1 < j2 ≤ B − 1).
  • It is possible to travel between any pair of cities by taking railways and/or buses.
  • 1 ≤ Ci ≤ 500 (0 ≤ i ≤ A − 1).
  • 1 ≤ Dj ≤ 500 (0 ≤ j ≤ B − 1).

예제

Here is a sample input for the sample grader and corresponding function calls.

Sample Input 1 Sample Calls
Call Call Return
4 3 4
0 1 6
2 1 4
2 0 10
1 2 3
3 1 1
3 2 3
3 0 7
InitA(4, 3, {0,2,2}, {1,1,0}, {6,4,10})    
  SendA(true)  
  SendA(false)  
InitB(4, 4, {1,3,3,3}, {2,1,2,0}, {3,1,3,7})    
  SendB(true)  
ReceiveA(true)    
ReceiveB(false)    
Answer()   {0,6,9,7}

서브태스크

번호배점제한
16

A = 0.

28

B ≤ 1 000.

38

A + B = N − 1.

438

N ≤ 900.

514

N ≤ 1 100.

610

N ≤ 1 400.

716

No additional constraints.

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.