시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB54161022.222%

문제

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?

입력

The first line contains two integers N and M, 1 ≤ N, M ≤ 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 ≤ u, v < N, 0 < w ≤ 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 ≤ s, t < N the number of the station closest to KTH and closest to home, respectively. It is possible to reach t from s.

출력

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.

예제 입력 1

4 4
0 1 100
0 2 100
1 3 100
2 3 100
0 3

예제 출력 1

0 3

예제 입력 2

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

예제 출력 2

0 3 6

출처

Contest > KTH Challenge > KTH Challenge 2014 G번

  • 문제를 만든 사람: Marc Vinyals