[BOJ]11657번 : 타임 머신

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

11657번: 타임머신

분류 : 벨만 포드 알고리즘

 

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

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    char nextChar() {
        return next().charAt(0);
    }
}

public class Main {

    public static PrintWriter out;
    public static final int inf = Integer.MAX_VALUE/2;
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
            
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] dist = new int[N];
        Vector<Edge>[] edge = (Vector<Edge>[]) new Vector[N];
        for(int i=0;i<N;i++)
        {
            edge[i] = new Vector<Edge>();
        }
        
        for(int i=0;i<M;i++)
        {
            int t1 = sc.nextInt();
            int t2 = sc.nextInt();
            int t3 = sc.nextInt();
            edge[t1-1].add(new Edge(t2-1,t3));
        }
        Arrays.fill(dist, inf);
        dist[0]=0;
        boolean cycle = false;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                for(Edge e: edge[j]){
                    int v = e.v;
                    int cost = e.cost;
                    if(dist[j]!=inf && dist[v]>dist[j]+cost){
                        dist[v] = dist[j] +cost;
                        if(i==N-1) cycle = true;
                    }
                }
            }
        }
        if(cycle) out.println(-1);
        else{
            for(int i=1;i<N;i++){
                out.println(dist[i]!=inf ? dist[i]: -1);
            }
        }        
        out.flush();
    }
}
class Edge {
    int v,cost;
    public Edge(int v, int cost){
        this.v=v;
        this.cost=cost;
    }
}

 

음수 간선치가 있기 때문에 벨만 - 포드 알고리즘으로 풀 수 있는 문제.

 

다른 코드들도 참조 하여 벨만 - 포드에 대해 공부하고 이해하려고 했지만

내게는 "라이" 라는 분의 블로그의 설명이 제일 잘 와닿아서 참조하여 문제 해결 완료..