059 : 타임머신으로 빨리 가기

 

우선순위는 필요없으나 에지중심 작업이므로 s와 e, 그리고 사이인 w를 사용할 Edge class 필요 

 

 

 

 

 

 

 

 

 

 

 

 

MSP처럼 최소거리부터 연결하기 위해 정렬시킬 필요가 있을 때에는 PQ에 에지를 (모두)넣고 (BFS없이)빼야 하지만

 

순서없이 단순히 모든 에지를 순회시켜 check-in으로 충분한 경우에는 Edge를 기반으로 하는 List만 만들고 넣어준다

 

 

 

 

 

receiver 필요

1이 sP이므로 0 설정

 

 

 

 

 

 

 

 

첫번째 for문은 단순반복이므로 while으로 대체하는게 편할수도 있다

 

모든 에지를 순회하되, 시작부터 INF 되는것은 거른다

크다 > 작다 에서 큰것 = 작은것 으로 할당

 

surviving boolean으로 return이 아닐 때에는 cont가 필요하다

 

더 작은 거리가 발생만 하면 변경작업 없이 바로 boolean으로 정보를 쏴주면 된다

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        // ISC
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        // D2F
        Edge[] edges = new Edge[E+1];
        for (int i = 1; i <= E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(s, e, w);
        }

        // receiver
        int[] D = new int[E+1];
        Arrays.fill(D, Integer.MAX_VALUE);
        D[1] = 0;

        // OP
        for (int i = 1; i <= V-1; i++) {
            for (int j = 1; j <= E; j++) {
                Edge edge = edges[j];
                if (D[edge.s] != Integer.MAX_VALUE
                        && D[edge.e] > D[edge.s] + edge.w)
                    D[edge.e] = D[edge.s] + edge.w;
            }
        }

        boolean mCycle = false;
        for (int i = 1; i <= E; i++) {
            Edge e = edges[i];
            if (D[e.s] != Integer.MAX_VALUE
                    && D[e.e] > D[e.s] + e.w)
                mCycle = true;
        }

        // OEC
        if (!mCycle) {
            for (int i = 2; i <= V; i++) {
                if (D[i] == Integer.MAX_VALUE)
                    System.out.println("-1");
                else
                    System.out.println(D[i]);
            }
        } else {
            System.out.println("-1");
        }

    }
}

class Edge {
    int s, e, w;
    public Edge(int s, int e, int w) {
        this.s = s;
        this.e = e;
        this.w = w;
    }
}