N17396 - 백도어

다익스트라를 처음 접한 나는 3일간 코드를 봤고 무척 힘들었다...

가장 핵심은 priority queue를 이용해 방문할 node들에서 "최소 거리 혹은 점수"를 가지는 애를 넣어야 한다는 것이다.

package dijkstra;

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class N17396 {
    static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
    static List<Node>[] nodes;
    static long[] dist;

    public static void main(String[] args) throws IOException{
        input();
        solution(0);
    }

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(BR.readLine());
        boolean[] visible;
        int n, m, v1, v2, score;

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());;
        nodes = new ArrayList[n];
        dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        visible = new boolean[n];

        st = new StringTokenizer(BR.readLine());
        for(int i=0; i<n; i++) {
            nodes[i] = new ArrayList<>();
            visible[i] = Integer.parseInt(st.nextToken()) == 1;
        }
        visible[n-1] = false;

        for ( int i = 0; i < m; i++ ) {
            st = new StringTokenizer(BR.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            score = Integer.parseInt(st.nextToken());
            if(visible[v1] || visible[v2]) continue;
            nodes[v1].add(new Node(v2, score));
            nodes[v2].add(new Node(v1, score));
        }
    }

    private static void solution(int start) {
        PriorityQueue<Node> path = new PriorityQueue<>();
        Node curNode;
        long tmp;

        dist[start] = 0;
        path.add(new Node(start, 0));

        while(!path.isEmpty()) {
            curNode = path.poll();
            if(dist[curNode.name] < curNode.value) continue;
            for(Node nxtNode : nodes[curNode.name]) {
                tmp = dist[curNode.name] + nxtNode.value;
                if(tmp < dist[nxtNode.name]) {
                    dist[nxtNode.name] = tmp;
                    path.add(new Node(nxtNode.name, dist[nxtNode.name]));
                }
            }
        }

        if(dist[dist.length-1] != Long.MAX_VALUE)
            System.out.println(dist[dist.length-1]);
        else System.out.println(-1);
    }

    static class Node implements Comparable<Node> {
        int name;
        long value;

        public Node(int name, long value) {
            super();
            this.name = name;
            this.value = value;
        }

        @Override
        public int compareTo(Node n) {
            return Long.compare(this.value, n.value);
        }
    }
}