시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 64 MB42141230.000%

문제

There are N computers in the computer classroom of a local secondary school and they are connected with cables to form a single network. Each cable joins two distinct computers. Some pairs of computers may not be joined by a cable directly, but a message can always be sent from any computer to any other computer through intermediate computers joined by cables. A message always chooses the shortest route to travel: the number of intermediate computers along its path (i.e. computers other than sender and receiver that the message visits) is minimised.

Adam and Billy, who use distinct computers a and b in this classroom, wish to determine a shortest route between their computers. They do not know the layout of the cables but they can send messages between all pairs of computers and calculate the number of intermediate computers that they visit.

However, Adam and Billy are not very good with computers and they ask you for help to achieve their goal without sending too many messages.

Find a shortest route between computers a and b without sending more messages than is allowed.

구현

You need to implement one procedure findRoute(N, a, b) that takes the following parameters:

  • N — the number of computers in the classroom (they are labelled from 1 to N)
  • a, b — the labels of Adam and Billy’s computers (a ≠ b and 1 ≤ a, b ≤ N)

Your procedure findRoute can call function ping(i, j) that takes as parameters labels of two distinct computers (i ≠ j and 1 ≤ i, j ≤ N) and returns the number of intermediate computers that a message travelling from i to j would visit.

Your procedure findRoute has to describe a shortest route that a message sent from a to b might take. This must be done by repeatedly calling procedure travelTo(k) that takes as parameter the label of computer to which the message should travel next (1 ≤ k ≤ N). The message starts at a, and whenever travelTo(k) is called, it moves to computer k.

In addition to the standard requirements (time and memory limits, no runtime errors), your submission has to achieve the following in order to solve a testcase:

  • the message must be at b when procedure findRoute terminates,
  • any two consecutive computers in its path must be joined by a cable,
  • it must take a shortest route,
  • the number M of calls to function ping must not exceed the allowed limit,
  • function ping and procedure travelTo must only be called with allowed parameter values.

예제

Consider the example shown in the diagram below (points correspond to computers, lines — to cables). There are N = 4 computers in total, and Adam and Billy are using computers a = 1 and b = 4.

The first call will be to procedure

findRoute(4, 1, 4).

Its sample behaviour could be as follows:

ping(1, 4) is called and returns 1, ping(1, 2) is called and returns 0, ping(2, 4) is called and returns 0.

This information is sufficient to determine that 1 → 2 → 4 is a shortest route from 1 to 4. This should be described as follows:

travelTo(2) is called, travelTo(4) is called, findRoute terminates.

제한

In all subtasks the constraint 2 ≤ N ≤ 1000 holds.

서브태스크

번호배점제한
125

between any two computers there is exactly one shortest route; M cannot exceed 2N.

225

M cannot exceed N2.

325

M cannot exceed 4N.

425

M cannot exceed 2N.

샘플 그레이더

The sample grader on your computer will read data from standard input. The first line of input should contain four integers N, a, b and the allowed limit for M. The next N lines should contain N integers each, describing the layout of the cables: the j–th integer in the i–th of these rows (i = j) should be the number of intermediate computers that a message sent from i to j would visit. It does not matter what the entries with i = j are.

The following input describes the above example with M limited by 100:

4 1 4 100
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0

제출할 수 있는 언어

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

채점 및 기타 정보

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