https://www.acmicpc.net/problem/11657
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
class Bus{
int start, end, weight;
public Bus(int start, int end, int weight){
this.start = start;
this.end = end;
this.weight = weight;
}
}
public class Main{
static int n, m;
static final int INF = 100000000;
static ArrayList<Bus> list = new ArrayList<>();
static long[] dist;
public static boolean bellmanFord(){
boolean cycle = false;
dist[1] = 0;
for(int i=0; i<=n; i++){
for(int j=0; j<m; j++){
int s = list.get(j).start;
int e = list.get(j).end;
int w = list.get(j).weight;
if(dist[s]!=INF && dist[s] + w < dist[e]){ // 목적지까지 최단 경로 > 시작점 최단 경로 + 목적지까지 가중치 일 때
dist[e] = dist[s]+w;
if(i==n) cycle = true; // n번의 라운드 반복 후에 n번째 라운드에서도 최단경로가 갱신되면 음의 사이클임
}
}
}
return cycle;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
dist = new long[n+1];
Arrays.fill(dist, 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());
list.add(new Bus(A, B, C));
}
StringBuilder sb = new StringBuilder();
if(bellmanFord()){
sb.append(-1+"\n");
}else {
for(int i=2; i<=n; i++){
sb.append(dist[i]==INF ? -1 : dist[i]).append("\n");
}
}
System.out.println(sb);
}
}
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 1644 - 소수의 연속합 (0) | 2023.01.26 |
---|---|
[JAVA] 백준 1806- 부분합 (0) | 2023.01.26 |
[JAVA] 백준 1541- 잃어버린 괄호 (0) | 2023.01.21 |
[JAVA] 백준 11404번- 플로이드 (0) | 2023.01.20 |
[JAVA] 백준 1202번- 보석 도둑 (0) | 2023.01.16 |