|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Training #5Ended |
G - Intercept
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Fatima commutes from KTH to home by subway every day. Today Robert decided to surprise Fatima by baking cookies and bringing them to an intermediate station. Fatima does not always take the same route home, because she loves to admire the artwork inside different stations in Stockholm. However, she always optimizes her travel by taking the shortest route. Can you tell Robert which station he should go to in order to surely intercept Fatima?
Input
The first line contains two integers $N$ and $M$, $1 \leq N,M \leq 100\,000$, where $N$ is the number of subway stations and $M$ is the number of subway links. $M$ lines follow, each with three integers $u$, $v$, $w$, $0 \leq u,v < N$, $0 < w \leq 1\,000\,000\,000$, meaning that there is a one-way link from $u$ to $v$ that takes $w$ seconds to complete. Note that different subway lines may serve the same route.
The last line contains two integers $s$ and $t$, $0 \leq s,t < N$ the number of the station closest to KTH and closest to home, respectively. It is possible to reach $t$ from $s$.
Output
A space separated list of all the station numbers $u$ such that all shortest paths from $s$ to $t$ pass through $u$, in increasing order.
Sample test(s)
Input
4 4
0 1 100
0 2 100
1 3 100
2 3 100
0 3
Output
0 3
Input
7 8
0 1 100
0 2 100
1 3 100
2 3 100
3 4 100
3 5 100
4 6 100
5 6 100
0 6
Output
0 3 6