N(1≤N≤500) 개의 도시, 버스가 M(1≤M≤6,000) 개
각 버스는 A, B, C로 나타낼 수 있는데 A는 시작도시, B는 도착도시, C는 버스를 타고 걸리는 데 걸리는 시간
-10,000 ≤ C ≤ 10,000
1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간은?
음수가 존재하는 최단거리이다. 출발 도착이 존재하기 때문에 방향 그래프이다.
1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다면 -1을 출력
⇒ 1번에서 출발해서 순환이 존재 + 비용의 합이 음수 = 무한히 오래 전으로 돌릴 수 있다.
도달할 수 없다 = 경로가 없다.
벨만-포드를 통해 음수 가중치를 처리 + 음수 사이클 감지
package boj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class BOJ11657 {
static class Edge {
int from;
int to;
int cost;
Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}
static FastReader scan = new FastReader();
static int N, M;
static Edge[] edges;
static void input() {
N = scan.nextInt();
M = scan.nextInt();
edges = new Edge[M];
for (int i = 0; i < M; i++) {
edges[i] = new Edge(scan.nextInt(), scan.nextInt(), scan.nextInt());
}
}
static void solve() {
long[] dist = new long[N + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[1] = 0;
boolean hasNegativeCycle = false;
for (int i = 1; i <= N; i++) {
for (Edge edge : edges) {
if (dist[edge.from] != Integer.MAX_VALUE &&
dist[edge.to] > dist[edge.from] + edge.cost) {
dist[edge.to] = dist[edge.from] + edge.cost;
if (i == N) {
// N인데도 갱신? -> 음수 사이클 존재
hasNegativeCycle = true;
break;
}
}
}
}
StringBuilder sb = new StringBuilder();
if (hasNegativeCycle) {
System.out.println(-1);
} else {
for (int i = 2; i <= N; i++) {
if (dist[i] == Integer.MAX_VALUE) {
sb.append(-1).append('\\n');
} else {
sb.append(dist[i]).append('\\n');
}
}
System.out.println(sb);
}
}
public static void main(String[] args) {
input();
solve();
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}
'Algorithm > BOJ' 카테고리의 다른 글
| BOJ 9370 - 미확인 도착지 (1) | 2024.11.15 |
|---|---|
| BOJ 10942 - 팰린드롬? (0) | 2024.11.12 |
| BOJ 4991 - 로봇 청소기 (0) | 2024.11.11 |
| BOJ 11049 - 행렬 곱셈 순서 (1) | 2024.11.09 |
| BOJ 6087 - 레이저 통신 (0) | 2024.11.07 |