Putovanje
레이팅 미적용의견: 0
Mr. Malnar has finally reached his annual vacation. The country he decided to
travel to can be represented as \(n\) cities and \(m\) bidirectional roads connecting them.
Each road has the same length, and it is possible to reach any city from any other
by traveling on these roads. A path from city \(a\) to city \(b\) is defined as a sequence
of roads such that, starting from city \(a\) and sequentially traversing the roads in
that sequence, one ends up in city \(b\). The length of a path is defined as the number
of roads on that path.
Mr. Malnar routinely booked the most expensive hotel in one of the cities and then started to plan his
journey. To facilitate his planning, he recorded the length of the shortest path needed from the hotel to
each city.
Excited about his lo\(ng-aw\)aited vacation, Mr. Malnar completely forgot in which city the hotel is located.
He certainly does not want to miss the trip, so he asks you to determine in which cities the hotel can be
located.
Subtask 1 (10 points): \(m + 1 = n \le 5000\), \(u_{i} + 1 = v_{i}\) for every \(i\)
Subtask 2 (20 points): \(d\)\(i\) = −1 for every \(i > 1\)
Subtask 3 (35 points): n, \(m \le 5000\)
Subtask 4 (45 points): No additional constraints.
In the first line, there are natural numbers \(n\) and \(m - th\)e number of cities and the number of roads
connecting them (\(1 \le n \le 5 \cdot 10^{4}\), \(n - 1 \le m \le 10^{5}\)).
In the \(i-th\) of the following \(m\) lines, there are numbers \(u_{i}\) and \(v_{i} - th\)ere is a road between cities \(u_{i}\) and \(v_{i}\)
(\(1 \le u_{i}\), \(v_{i} \le n\), \(u_{i}\)̸ = \(v_{i}\)). There is at most one road between any two cities.
In the last line, there are \(n\) intege\(rs - th\)e \(i-th\) number \(d\)\(i\) indicates the distance from the \(i-th\) city to the
city where the hotel is located, \(or - 1\) if Mr. Malnar did not record that distance (−\(1 \le d_{i} < n\)).
In the first line, write the number of cities where the hotel can be located.
In the second line, write the labels of the cities where the hotel can be located, in ascending order.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(m + 1 = n \le 5000\), \(u_{i} + 1 = v_{i}\) for every \(i\) |
2 | 20점 | \(d\)\(i\) = −1 for every \(i > 1\) |
3 | 35점 | n, \(m \le 5000\) |
4 | 45점 | No additional constraints. |
7 6
1 2
1 3
3 4
3 5
3 6
5 7
2 -1 -1 -1 -1 -1 32
4 66 6
1 2
2 3
3 4
4 5
5 6
6 1
2 -1 -1 1 -1 -12
3 54 3
1 2
2 3
3 4
1 -1 -1 10Clarification of the first example:
The path from the city labeled 4 to the city labeled 1 is of length 2, while the path from the city labeled 4
to the city labeled 7 is of length 3. Therefore, city 4 satisfies both conditions and the hotel can be located
there.
The same holds true for the city labeled 6.
평가 및 의견
Putovanje
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Putovanje