以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
ICPC 2024–2025, NERC – Northern Eurasia Finals
St. Petersburg, Novosibirsk, Astana, Tbilisi, December 15th, 2024
Problem I. Incompetent Delivery Guy
Time limit: 3 seconds
Memory limit: 1024 megabytes
In Isengard, wizard Saruman, with the help of some magic spells, organized a transport system between
n towers. To be precise, he created m one-directional passages, each connecting two towers. Each passage
i has some number ti associated with it, meaning the time it takes, in seconds, for an orc to travel along
it. In other words, Saruman’s transport system can be represented with a directed weighted graph.
On December 15th, Saruman, sitting in the middle tower called Orthanc, gets a message from Sauron
(via palantir) which says that a valuable present is already near Isengard’s entrance tower. So, Saruman
needs to instruct the garrison to select one of the orcs and send them with a gift along the shortest path
from the entrance tower to Orthanc.
Unfortunately, orcs... aren’t exactly smart fellas. Although they are able to drag a load along passages
in the transport system and they (at least, in principle) know where Orthanc is, orcs have a really
poor understanding of the concept of the shortest path. To make everyone’s lives easier, on some towers
Saruman puts a huge flashing pointer which says “TO ORTHANC — THIS WAY” and points to
one of the passages leading from this tower. Saruman wants orcs to reach Orthanc as fast as possible —
hence, a flashing pointer can only point to a passage that lies on one of the shortest paths to Orthanc.
−→ −−→Formally, the flashing pointer on the tower u can point to a passage ⃗a = uv only if dist(v, O) < +∞and
−−→ −−→ −−→
dist(u, O) = t⃗a + dist(v, O). Here by dist(x, y) we denote the minimum time it takes to get to tower y
from tower x (or +∞if there is no oriented path from x to y), by O we denote the tower of Orthanc, and
by u and v we denote the starting and the finishing towers of the passage ⃗a. Note that Saruman will not
put a flashing pointer onto Orthanc, nor will he put it on any tower from which Orthanc is unreachable.
On each of the remaining towers, he will put exactly one flashing pointer.
This still does not work perfectly well. While traveling to Orthanc, each time an orc is near some tower
(any but Orthanc), the orc can either choose a marked passage with Saruman’s sign or do some hanging
around, as Saruman calls it, when the orc chooses an outgoing passage completely at random. For any
orc, there exists an integer d such that when they’re given an order to go to Orthanc, during the commute
the orc never chooses to hang around more than d times. This exact number we will politely call this orc’s
incompetence.
Note that at some moment it may happen that an orc finds themselves near a tower from which there is
no oriented path to Orthanc. Under these unfortunate circumstances, even the least competent orc will
find no flashing pointer on the tower, figure out that their mission has failed, stop immediately, and wait
for a rescue operation.
Saruman knows that his servants are not very brilliant minds, so he does not expect the delivery of the
present to be quick, but he wants it to be successful at the very least. Therefore, it makes sense to assign
to this task as competent an orc as possible; on the other hand, competent orcs are rare and pulling
them out of their current activities may entirely disrupt those activities. Hence, given the description of
Isengard’s transport system, find the maximum number d such that there exists a way Saruman can put
the flashing pointers, so that an orc with a level of incompetence equal to d can be assigned to deliver the
present from the entrance tower and is guaranteed to carry out the order with success, reaching Orthanc.
Input
The first line contains two integers n and m — the number of towers and the number of one-directional
passages between them (2 ≤n ≤4 · 105; 0 ≤m ≤4 · 105). In the next m lines the descriptions of the
passages follow. Each line contains three integers ui, vi, ti — the numbers of the starting and the ending
towers of a passage, and the number of seconds it takes for a loaded orc to travel along this passage
(1 ≤ui, vi ≤n; 1 ≤ti ≤106). There can be several passages between the same pair of towers, in any
direction, as well as passages that lead from a tower to itself — in other words, loops, multiple passages,
and symmetric pairs of passages are allowed.
Page 11 of 19
ICPC 2024–2025, NERC – Northern Eurasia Finals
St. Petersburg, Novosibirsk, Astana, Tbilisi, December 15th, 2024
The entrance tower is numbered 1 and Orthanc is numbered n.
Output
Print one integer d — the maximum incompetence of an orc who is guaranteed to complete the delivery.
If with any level of incompetence it is possible, print the number n (the number of towers). On the other
hand, if with any level of incompetence it is impossible, print −1.
Examples
standard input standard output Illustration
5 7 2
3 4 2
1 3 5 3 8
4 5 2
5 2
3 4 3 5 11
1 5 9
1 5
4 2 8 9
5 2 11
3 5 5
6 6 -1 5
1 2 5
1 2 6
2 3 9
1000000
1 4 11
11 9 1
2 1 1000000
5 3 15
4 3 5
5 6 1 15
4 7 4 5
1 2 5 11
4 1 2 3
1 1 30 16 9
1000000
3 2 9 11
1 4 11 30
1 4 16
2 1 1000000
1 4 11
2 0 -1
1 2
6 7 1 2
1 2 5 6 5
2 3 9
11 9 4
1 6 11
2 1 1000000
1 5 9 1 5 2 3 4
9
5 6 2 1000000
5 4 4
4 4 1
2 3
1 4 6 3
1 3 2 2
3 2 3 4
3 4 4
1 4
6
3 2 0
2 1 3
1 2 1 1 1
1 3 1
Page 12 of 19