Informatica Online Judge

  간단한 다익스트라문제 [2461 / 099D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 40   Total Tried : 250


The Champion of this Problem (C++) : gs18116 - ms / 952byte
My Best Submission (C++) : N/A

[36th 최은수(gs18115)]
Writer ID : [gs18115]

Background

방향성이 있고, 간선에 가중치가 있는 그래프 하나가 주어진다.

그래프의 간선 중 최대 한 개가 음수 가중치를 갖는다고 한다.

이 때, 1번 정점부터 모든 정점까지 최단 경로를 구하여라.

Input

첫 줄에 정점의 수 V와 간선의 수 E가 주어진다. (1 <= V,E <= 500,000)

다음 E줄에는 한 줄에 세 숫자 u,v,w가 주어진다. u에서 v로 가는 가중치 w의 간선이 있다는 뜻이다. (1 <= u,v <= V, 1 <= |w| <= 10^9)

Output

만약 음수 사이클이 있다면, 첫 줄에 -1만을 출력한다.

음수 사이클이 없다면, V개의 수를 공백으로 구분하여 한 줄에 출력한다.

i번째 수는 1번 정점부터 i번 정점까지의 최단 경로를 의미하고, 1번 정점에서 시작하여 i번 정점에 도착할 수 없다면 최단 경로 대신 -1을 출력한다.

IO Example

입력
2 1
1 2 -1

출력
0 -1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]