[Java] 백준 - 1504번: 특정한 최단 경로

6월 21일(금) - 그래프와 순회(1504번)

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

---

최초 생각 정리

---

문제점

---

풀이

(풀이참고 -> https://steady-coding.tistory.com/82)

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

import java.util.*;

class Node implements Comparable<Node>{
    int end;
    int weight;
    Node(int end, int weight){
        this.end = end;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o){
        return weight - o.weight;
    }
}
public class Main {

    static int N,E,v1,v2;
    static int[] dist;
    static boolean[] visited;
    static List<List<Node>> nodelist = new ArrayList<>();
    static int INF = 200000000;

    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());
        dist = new int[N+1];
        visited = new boolean[N+1];

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

        for(int i=0; i<E; i++)
        {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            nodelist.get(start).add(new Node(end, weight));
            nodelist.get(end).add(new Node(start, weight));
        }

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

        int res1 = 0;
        res1 = res1 + dijkstra(1, v1);
        res1 = res1 + dijkstra(v1, v2);
        res1 = res1 + dijkstra(v2, N);

        int res2 = 0;
        res2 = res2 + dijkstra(1, v2);
        res2 = res2 + dijkstra(v2, v1);
        res2 = res2 + dijkstra(v1, N);

        int min_length = (res1 >= INF && res2 >= INF) ? -1 : Math.min(res1, res2);
        System.out.println(min_length);
    }

    public static int dijkstra(int start, int end){
        Arrays.fill(dist, INF);
        Arrays.fill(visited, false);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[N+1];
        pq.add(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty())
        {
            Node cur_node = pq.poll();
            int cur = cur_node.end;
            if(!visited[cur])
            {
                visited[cur] = true;
                for(Node node : nodelist.get(cur))
                {
                    if(!visited[node.end] && dist[node.end] > dist[cur] + node.weight)
                    {
                        dist[node.end] = dist[cur] + node.weight;
                        pq.add(new Node(node.end, dist[node.end]));
                    }
                }
            }
        }

        return dist[end];
    }
}

---