백도어 - 17396번

---

풀이 방법

다익스트라로 최단 경로를 구하는 문제이다.

최단 경로를 구하는 과정에서 지나간 지점인지 확인할 때 시야가 보이는 지점인지 확인해서 경로를 지나가지 않도록 설정하고 시야가 보이더라도 넥서스라면 경로가 지나가도록해서 최단경로를 구하도록 구현했다.

 

내 코드

package com.company;

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

class Node implements Comparable<Node> {
    private int index;
    private Long distance;

    public Node(int index, Long distance) {
        this.index = index;
        this.distance = distance;
    }

    public int getIndex() {
        return index;
    }

    public Long getDistance() {
        return distance;
    }

    @Override
    public int compareTo(Node other) {
        if (this.distance < other.getDistance())
            return -1;
        return 1;
    }
}

public class Main {

    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static Long[] d;
    static int[] array;
    static int n, m;

    static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0L));
        d[0] = 0L;

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            Long dist = node.getDistance();
            int nowIndex = node.getIndex();

            if (d[nowIndex] < dist)
                continue;

            for (int i = 0; i < graph.get(nowIndex).size(); i++) {
                Long temp = graph.get(nowIndex).get(i).getDistance() + d[nowIndex];
                if (temp < d[graph.get(nowIndex).get(i).getIndex()]
                        && (array[graph.get(nowIndex).get(i).getIndex()] == 0 || graph.get(nowIndex).get(i).getIndex() == n - 1))
                {
                    d[graph.get(nowIndex).get(i).getIndex()] = temp;
                    pq.offer(new Node(graph.get(nowIndex).get(i).getIndex(), temp));
                }
            }
        }


    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        array = new int[n];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        d = new Long[n];

        Arrays.fill(d, Long.MAX_VALUE);

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<Node>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            Long t = Long.parseLong(st.nextToken());

            graph.get(a).add(new Node(b, t));
            graph.get(b).add(new Node(a, t));
        }

        dijkstra();

        if (d[n - 1] == Long.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(d[n - 1]);
    }
}