문제
N개의 도시와 M개의 버스 노선(음의 가중치 가능)이 주어질 때, 1번 도시에서 나머지 도시까지의 최단 거리를 구하라. 음의 사이클이 있으면 -1을 출력한다.
입력
첫째 줄에 N, M, 이후 M줄에 출발, 도착, 시간이 주어진다.
출력
음의 사이클이 있으면 -1, 아니면 2~N번 도시까지의 최단 거리를 한 줄씩 출력한다. 경로가 없으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 4 1 2 4 1 3 3 2 3 -1 3 1 -2 | 4 3 |
풀이
벨만-포드 알고리즘으로 음의 가중치 간선이 있는 그래프의 최단 경로를 구한다.
- N-1번 모든 간선에 대해 완화(relaxation)를 수행한다
- 갱신이 없으면 조기 종료한다
- N번째 반복에서 갱신이 발생하면 음의 사이클이 존재한다
- 도달 불가능한 노드(
dist == INF)는 완화 대상에서 제외한다
핵심 아이디어: 벨만-포드는 N-1번 반복으로 최단 경로를 확정하고, N번째 반복의 갱신 여부로 음의 사이클을 판별한다. long 타입을 사용하여 오버플로우를 방지한다.
코드
package day549;
import java.io.*;
import java.util.*;
public class Day501BOJ11657타임머신 {
static int N, M;
static ArrayList<ArrayList<City>> a;
static long[] dist;
static final int INF = 987654321;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
a = new ArrayList<>();
dist = new long[N + 1];
for (int i = 0; i <= N; i++) {
a.add(new ArrayList<>());
dist[i] = INF;
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
a.get(A).add(new City(B, C));
}
StringBuilder sb = new StringBuilder();
if (bellmanFord()) {
sb.append("-1\n");
} else {
for (int i = 2; i <= N; i++) {
if (dist[i] == INF) {
sb.append("-1\n");
} else {
sb.append(dist[i] + "\n");
}
}
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static boolean bellmanFord() {
dist[1] = 0;
boolean update = false;
for (int i = 1; i < N; i++) {
update = false;
for (int j = 1; j <= N; j++) {
for (City city : a.get(j)) {
if (dist[j] == INF) {
break;
}
if (dist[city.end] > dist[j] + city.weight) {
dist[city.end] = dist[j] + city.weight;
update = true;
}
}
}
if (!update) {
break;
}
}
if (update) {
for (int i = 1; i <= N; i++) {
for (City city : a.get(i)) {
if (dist[i] == INF) {
break;
}
if (dist[city.end] > dist[i] + city.weight) {
return true;
}
}
}
}
return false;
}
static class City {
int end;
int weight;
City(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
}복잡도
- 시간: O(VE)
- 공간: O(V)