택배 배달
골드 V의견: 0
택배 기사 민준이는 창고(도시 \(1\))에서 출발해 \(N\)개의 도시에 소포를 배달한다. 도시 사이에는 \(M\)개의 단방향 도로가 있으며, 각 도로에는 통행료가 있다. 통행료가 음수인 도로는 보조금을 받는 구간이다.
음수 사이클은 존재하지 않는다.
창고(도시 \(1\))에서 각 도시까지의 최단 거리를 구하여라. 도달할 수 없는 도시는 \(-1\)을 출력한다.
- \(1 \le N \le 500\)
- \(0 \le M \le 5\,000\)
- \(-10^6 \le w \le 10^6\)
- 음수 사이클은 없다.
첫째 줄에 도시의 수 \(N\)과 도로의 수 \(M\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 도로 정보 \(u\), \(v\), \(w\)가 주어진다. \(u\)에서 \(v\)로 가는 통행료가 \(w\)인 단방향 도로를 의미한다.
\(N\)개의 줄에 걸쳐 도시 \(1\)부터 \(N\)까지 각 도시까지의 최단 거리를 출력한다. 도달할 수 없으면 \(-1\)을 출력한다.
4 4
1 2 3
1 3 -1
2 4 5
3 4 2
0
3
-1
1
창고(노드 \(1\))에서 출발한다. \(1\to2\)는 거리 \(3\), \(1\to3\)은 \(-1\), \(1\to4\)는 \(1\to3\to4\)를 거쳐 \(-1+2=1\)이 최소이다.
3 3
1 2 5
2 3 -3
1 3 10
0
5
2
\(1\to3\)은 직접 가면 \(10\)이지만 \(1\to2\to3 = 5+(-3) = 2\)가 더 짧다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
택배 배달
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
택배 배달