특정한 최단 경로 - 1504번

---

풀이 방법

bfs를 이용해서 최단 경로를 구하는 메소드를 만들어서 

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

두 가지 경로로 나눠서 계산해주었다.

 

내 코드

package com.company;

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

public class Main {
    static int N, E, v1, v2;
    static ArrayList<ArrayList<Node>> list = new ArrayList<>();
    static boolean[] visited;

    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());
        E = Integer.parseInt(st.nextToken());
        visited = new boolean[N + 1];

        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());

            list.get(x).add(new Node(y, z));
            list.get(y).add(new Node(x, z));
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(list.get(i));
        }

        st = new StringTokenizer(br.readLine());
        v1 = Integer.parseInt(st.nextToken());
        v2 = Integer.parseInt(st.nextToken());

        long x = bfs(1, v1);
        long y = bfs(v1, v2);
        long z = bfs(v2, N);

        long a = bfs(1, v2);
        long b = bfs(v2, v1);
        long c = bfs(v1, N);

        long len = Long.MAX_VALUE;

        if (x != -1 && y != -1 && z != -1)
            len = x + y + z;
        if (a != -1 && b != -1 && z != -1)
            len = Math.min(a + b + c, len);

        if (len == Long.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(len);

    }

    static long bfs(int v, int N) {
        if (v == N) {
            return 0;
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(v, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if (node.getDes() == N) {
                Arrays.fill(visited, false);
                return node.getLen();
            }

            if(!visited[node.getDes()]){
                visited[node.getDes()] = true;
                for (int i = 0; i < list.get(node.getDes()).size(); i++) {
                    Node a = list.get(node.getDes()).get(i);

                    if (!visited[a.getDes()]) {
                        pq.add(new Node(a.getDes(), node.getLen() + a.getLen()));
                    }
                }
            }
        }

        Arrays.fill(visited, false);
        return -1;
    }
}

class Node implements Comparable<Node> {
    private int des;
    private long len;

    public int getDes() {
        return des;
    }

    public Node(int des, long len) {
        this.des = des;
        this.len = len;
    }

    public long getLen() {
        return len;
    }

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