[Gold4-JAVA] 백준 11657 - 타임머신

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

11657번: 타임머신

 

 

🤔문제 풀이

문제에서 음의 가중치가 존재하는 것,

그리고 1번 도시에서 어떤도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다 는 것에서

음의 사이클이 존재할 수도 있다는 정보를 얻어  한 정점에서 다른 정점까지 최단 거리를 구하고 음의 사이클 존재 여부를 확인할 수 있는 벨만 포드 알고리즘을 적용해 풀어야겠다고 생각했다.

🚨CODE

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		final long max = Long.MAX_VALUE;
		ArrayList<edge> list = new ArrayList<>();
		
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			list.add(new edge(start, end, cost));
		}
		
		long[] dist = new long[n+1];
		Arrays.fill(dist, max);
		dist[1] = 0;
		
		for(int i = 1; i<=n; i++) {
			for(edge e : list) {
				if(dist[e.start] == max) // 아직 방문하지 않은 정점이면 통과
					continue;
				
				// 현재 end정점까지의 거리가 start + cost 보다 큰 경우 갱신
				if(dist[e.end] > dist[e.start] + e.cost) {
					dist[e.end] = dist[e.start] + e.cost;
					
					// 마지막까지 값의 갱신이 일어난다는 것은 음의 사이클이 존재한다는 것
					if(i == n) {
						System.out.println(-1);
						return;
					}
				}
			}
		}
		
		for(int i = 1; i<=n; i++) {
			// dist[i]가 max인 것은 도달할 수 없는 정점이 존재한다는 것
			if(dist[i] == max) {
				System.out.println(-1);
				break;
			}else
				System.out.println(dist[i]);
		}
	}
}
class edge{
	int start;
	int end;
	int cost;
	public edge(int start, int end, int cost) {
		this.start = start; this.end = end; this.cost = cost;
	}
}