14284_간선 이어가기 2 *****

사용 알고리즘: 다익스트라...

사용 언어: java

 

package src.alStudy02;

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

public class Main_bj_14284_간선이어가기2 {
    static int n, m;
    static ArrayList<Node>[] al; //인접 리스트
    static int s, t; //시작점, 종착점
    static int[] dp;

    public static void main(String[] args) throws IOException {
        input_14284();

        System.out.println(dfs_14284(s, t));
    }

    private static int dfs_14284(int s, int t) {
        dp[s] = 0; //시작점은 0으로 초기화

        // ** 우선순위 큐를 쓰는 게 중요
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.value - o2.value); //가중치 순서대로 정렬
        pq.offer(new Node(s, 0));

        // ** 다익스트라
        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            for (Node nxt : al[cur.node]) {
                if (dp[nxt.node] > dp[cur.node] + nxt.value) {
                    dp[nxt.node] = dp[cur.node] + nxt.value;
                    pq.offer(new Node(nxt.node, dp[nxt.node]));
                }
            }
        }
        // ** 다익스트라

        return dp[t];
    }

    private static void input_14284() 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()); //간선 개수

        dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);

        al = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            al[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) -1;
            int b = Integer.parseInt(st.nextToken()) -1;
            int val = Integer.parseInt(st.nextToken());

            //무방향이므로 둘 다 add
            al[a].add(new Node(b, val));
            al[b].add(new Node(a, val));
        }

        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken()) -1;
        t = Integer.parseInt(st.nextToken()) -1;
    }
}

class Node {
    int node;
    int value;

    public Node(int node, int value) {
        this.node = node;
        this.value = value;
    }
}

 

 

느낀점:

우선순위 큐를 사용하라 이거야악~!