백준 5944번
https://www.acmicpc.net/problem/5944

문제

---

생각하기

---

• 다익스트라를 통해서 최단 거리를 구하면 되는 문제이다.

동작

        int[] dist = dijkstra(PB);

        if (dist[PA1] > dist[PA2]) {
            ans += dist[PA2];
            dist = dijkstra(PA2);
            ans += dist[PA1];
        } else {
            ans += dist[PA1];
            dist = dijkstra(PA1);
            ans += dist[PA2];
        }

그리디 방식으로 처음 출발하는 위치에서 짧은 길이를 먼저 선택하면 된다.

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final int INF = Integer.MAX_VALUE;
    private static int C, P, PB, PA1, PA2;
    private static List<List<Node>> adjList;

    private static class Node implements Comparable<Node> {
        int num;
        int weight;

        private Node(int num, int weight) {
            this.num = num;
            this.weight = weight;
        }

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

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();


        int ans = 0;
        int[] dist = dijkstra(PB);

        if (dist[PA1] > dist[PA2]) {
            ans += dist[PA2];
            dist = dijkstra(PA2);
            ans += dist[PA1];
        } else {
            ans += dist[PA1];
            dist = dijkstra(PA1);
            ans += dist[PA2];
        }

        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static int[] dijkstra(int start) {
        PriorityQueue<Node> pQue = new PriorityQueue<>();
        boolean[] isVisited = new boolean[P + 1];
        int[] dist = new int[P + 1];

        Arrays.fill(dist, INF);
        dist[start] = 0;
        pQue.offer(new Node(start, 0));

        while (!pQue.isEmpty()) {
            Node current = pQue.poll();

            if (dist[current.num] < current.weight) continue;
            if (isVisited[current.num]) continue;
            isVisited[current.num] = true;

            for (Node next : adjList.get(current.num)) {
                if (dist[next.num] <= dist[current.num] + next.weight) continue;
                dist[next.num] = dist[current.num] + next.weight;
                pQue.offer(new Node(next.num, dist[next.num]));
            }
        }

        return dist;
    } // End of dijkstra()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        PB = Integer.parseInt(st.nextToken());
        PA1 = Integer.parseInt(st.nextToken());
        PA2 = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < C; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            adjList.get(a).add(new Node(b, c));
            adjList.get(b).add(new Node(a, c));
        }

    } // End of input()
} // End of Main class