Baltazar
레이팅 미적용의견: 0
Baltazar decided to go on a vacation. Currently, he is in Baltazargrad, and wants
to travel to Primošten. To get there, he has to go through many cities. There are
\(n\) citites, and they are connected with \(m\) t\(wo-wa\)y roads. Baltazargrad is labeled
as city no. 1, and Primošten as city no. \(n\).
Baltazar isn’t sure about the route from Baltazargrad to Primošten, so he will use
GPS. It will lead him to his destination using the shortest route.
But Baltazar really likes to travel, and he can pour his magic potion on any road
(even the ones he won’t pass by), and increase its length by 2 kilometers. He can pour it on only one
road.
Soon he realized that he has to che\(ck-in\) in the hotel Zora in Primošten before noon, so he can’t increase
the length of the shortest route too much. Now, he wants to know how many roads can he pour his magic
potion on, so that the shortest distance between Baltazargrad and Primošten increases by exactly 1
kilometer.
Help him determine the roads he can pour his magic potion on.
Subtask 1 (15 points): n, \(m \le 1\,000\)
Subtask 2 (30 points): There is a road between Baltazargrad and Primošten, and its length is 1 kilometer longer than the shortest distance between these cities.
Subtask 3 (65 points): No additional constraints.
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 10\,000\)).
The description of the test cases follows.
The first line of each test case contains integers \(n\) and \(m\) (\(2 \le n \le 300\,000\), \(1 \le m \le mi\)n(300 000, {n}{(}{−}
2
),
the number of cities, and the number of roads between cities.
The following \(m\) lines contain integers \(a_{i}\), \(b_{i}\) i \(w_{i}\) (\(1 \le a_{i}\), \(b_{i} \le n\), \(a_{i}\)̸ = \(b_{i}\), \(1 \le w_{i} \le 10^{9}\)), meaning there is
a road between cities \(a@@RISE_MATH_BLOCK_0@@i\), and its length is \(w\)\(i\). Between each pair of cities, there is at most one road
connecting them.
All the cities are connected, i.e., for each pair of cities, there is a path from one to another, but not
necessary direct.
It is guaranteed that the sum of \(n\) over all test cases does not exceed 300 000, and that the sum of \(m\) over
all test cases does not exceed 300 000.
In the first line, print the integer \(c\), the number of roads on which Baltazar can pour his magic potion. In
the second line, print \(c\) integers, the indices of the roads in increasing order.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | n, \(m \le 1\,000\) |
2 | 30점 | There is a road between Baltazargrad and Primošten, and its length is 1 kilometer longer than the shortest distance between these cities. |
3 | 65점 | No additional constraints. |
3
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 3
5 6 2
6 7
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
1 6 72
2 4
0
3
2 4 6Clarification of the example:
The cities and the roads are shown in the image. If Baltazar pours his magic potion on road 2 (between
cities 1 and 3), or on road 4 (between cities 3 and 5), then the shortest distance between cities 1 and n
will increase by 1.
평가 및 의견
Baltazar
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Baltazar