의도된 시간복잡도
🔒시간 제한
2.000 S메모리 제한
512 MB제출 수
2정답 수
2정답률
100.000%
문제 설명
$N$개의 정점과 가중치 있는 $M$개의 간선으로 이루어진 유향 그래프 $G$가 주어진다. $1$번 정점으로부터 $2, 3, ... , N$번 정점으로의 최단 경로를 모두 구해보자. $G$는 다음을 만족한다.
- 자기 자신에게 향하는 간선은 존재하지 않는다.
- 어떤 두 정점을 직접적으로 잇는 간선은 두 개 이상 존재하지 않는다.
입력 설명
첫째 줄에 $N, M$이 공백으로 구분되어 주어진다. $(2 ≤ N ≤ 50,000; 1 ≤ M ≤ 200,000)$
둘째 줄부터 $M$개의 줄에 걸쳐 $u, v, w$가 공백으로 구분되어 주어진다. $(1 ≤ u, v ≤ N; 1 ≤ w ≤ 10^9)$ 이는 정점 $u$에서 정점 $v$로 향하는 가중치 $w$의 간선이 존재한다는 의미이다.
둘째 줄부터 $M$개의 줄에 걸쳐 $u, v, w$가 공백으로 구분되어 주어진다. $(1 ≤ u, v ≤ N; 1 ≤ w ≤ 10^9)$ 이는 정점 $u$에서 정점 $v$로 향하는 가중치 $w$의 간선이 존재한다는 의미이다.
출력 설명
첫째 줄에 $1$번 정점으로부터 $2, 3, ... , N$번 정점에 도달하는 최단 거리를 공백으로 구분하여 출력한다. $1$번 정점으로부터 도달할 수 없는 정점의 최단 거리는 $-1$이다.
예시 1
입력
8 9
1 2 1
2 3 2
2 5 10
3 4 3
4 5 3
5 6 2
4 6 3
6 7 3
1 7 1
출력
1 3 6 9 9 1 -1
기여
만든 사람 : pill27211