[백준(Baekjoon)][자바(java)] 11657 : 타임머신 / 최단 경로

 

www.acmicpc.net/problem/11657

11657번: 타임머신

 

문제 풀이

 

-   방향 그래프의 벨만 포드( bellman-ford ) 알고리즘 문제

 ☞  하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구함. ( 단일 시작점 최단 경로 문제 )
      음의 가중치를 허용. 가중치 합이 음인 사이클은 절대 허용하지 않음.
      간선을 최대 1개 사용하는 최단 경로, 최대 2개, ... 식으로 최대 n-1개 사용하는 최단 경로까지 구해나감

-   인접 리스트로 그래프 표현

-   ( 배열의 0부터 사용하기 위해 정점 번호 입력받을 때 1씩 뺌 )

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static class Node {
		int u, v, w;	// vertex num, vertex_connected num, weight
		Node( int u, int v, int w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
	}
	
	static final int max = Integer.MAX_VALUE;

	public static long[] bellmanFord( long d[], List<List<Node>> e, int s, int n ) {
		int i, k, u, v, w; long d_v;
		for( i = 0; i < n; i++ )
			d[i] = max; 
		d[s] = 0;	
		for( k = 0; k < n-1; k++ ) {
			for( u = 0; u < n; u++ ) {
				if( d[u] == max )  continue;
				for( Node nd : e.get(u) ) {
					v = nd.v;
					w = nd.w;
					d_v = d[u] + w;
					if( d[v] > d_v )
						d[v] = d_v;
				}
			}
		}
		for( u = 0; u < n; u++ ) {
			if( d[u] == max )  continue;
			for( Node nd : e.get(u) ) {
				v = nd.v;
				w = nd.w;
				d_v = d[u] + w;
				if( d[v] > d_v )
					return new long[] {};
			}
		}
		return d;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() ), 
		    m = Integer.parseInt( st.nextToken() ), i, j;
		long d[] = new long[n];
		List<List<Node>> e = new ArrayList<>();
		int a[] = new int[3];
		for( i = 0; i < n; i++ )
			e.add( new ArrayList<Node>() );
		for( i = 0; i < m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 3; j++ ) 
				a[j]  = Integer.parseInt( st.nextToken() ) - 1;
			a[2]++;
			e.get( a[0] ).add( new Node( a[0], a[1], a[2] ) );
		}
		br.close();
		
		d = bellmanFord( d, e, 0, n );
		
		StringBuilder sb = new StringBuilder();
		int len = d.length;
		if( len == 0 )
			sb.append( -1 );
		else {
			for( i = 1; i < n; i++ )
				sb.append( ( d[i] == max ? -1 : d[i] ) + "\n" );
		}
		System.out.println( sb.toString() );
	}
}