시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 256 MB | 34 | 10 | 10 | 34.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)
N
is N, the number of cities.A
is A, the number of railway lines.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).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)
x
represents the character sent from Baijan: true
for character 1, and false
for character 0.std::vector<int> Answer()
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)
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)
N
is N, the number of cities.B
is B, the number of bus lines.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).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)
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)
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.
ReceiveA
or ReceiveB
is executed. However, if both QX and QY are not empty, it is not determined whether ReceiveA
or ReceiveB
is executed.SendA
is executed during executions of ReceiveA
, the sent character is pushed to QY.SendB
is executed during executions of ReceiveB
, the sent character is pushed to QX.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).
Wrong Answer [1]
” to the standard error. It writes nothing to the standard output.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.
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} |
번호 | 배점 | 제한 |
---|---|---|
1 | 6 | A = 0. |
2 | 8 | B ≤ 1 000. |
3 | 8 | A + B = N − 1. |
4 | 38 | N ≤ 900. |
5 | 14 | N ≤ 1 100. |
6 | 10 | N ≤ 1 400. |
7 | 16 | No additional constraints. |
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)