ALGORITHM

[JAVA] 백준 11657- 타임머신(벨만 포드)

연듀 2023. 1. 23. 20:43

https://www.acmicpc.net/problem/11657

 

11657번: 타임머신

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

www.acmicpc.net

 

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