[백준] 타임머신 11657 - JAVA

문제

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

11657번: 타임머신

 

풀이

문제를 보면 한 도시에서 여러 도시로 이동할 수 있다고 한다. 그렇다면 쓸 수 있는건 그래프 알고리즘의 다익스트라와 벨만포드이다.

이때 시간은 음수가 나올 수 있다고한다. 그렇다면 벨만 포드 알고리즘을 이용하면 된다.

벨만포드 알고리즘은 다음 글을 참고하면 된다.

https://velog.io/@suk13574/알고리즘Java-벨만-포드Bellman-Ford-알고리즘

 

코드

import java.io.*;
import java.util.*;

public class Main {	 
	
	static int n, m;
	static int arr[][];
	static long dist[];
	
	public static void main(String[] args) throws Exception {
		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];
		arr = new int [m+1][3];
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
			arr[i][2] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.fill(dist, Integer.MAX_VALUE);
		
		dist[1] = 0;
		
		for(int i=1;i<n;i++) {
			for(int j=0;j<m;j++) {
				int out = arr[j][0];
				int in = arr[j][1];
				int w = arr[j][2];
				if(dist[out] != Integer.MAX_VALUE && dist[in] > dist[out] + w) {
					dist[in] = dist[out] + w;	
				}
			}
		}
		
		//음의 사이클 확인
		for(int i=0;i<m;i++) {
			int out = arr[i][0];
			int in = arr[i][1];
			int w = arr[i][2];
			
			if(dist[out] != Integer.MAX_VALUE && dist[in] > dist[out] + w) {
				System.out.print("-1");
				return;
			}
		}
		
		
		for(int i=2;i<=n;i++) {
			if(dist[i] == Integer.MAX_VALUE)
				System.out.println(-1);
			else
				System.out.println(dist[i]);
		}
		
		
	}
	

}