[BOJ] 백준 14284. 간선 이어가기2

문제

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

14284번: 간선 이어가기 2

---

풀이

전형적인 다익스트라 문제입니다. 

 

다익스트라 알고리즘을 사용할 수 있는 조건이 몇 가지가 있습니다.

 

1. 가중치는 모두 0 이상이어야 한다.

2. 방향 그래프를 가정으로 둔다. 

3. 사이클이 없어야 한다.

 

위 문제에서는 무방향 그래프가 주어졌기 때문에, 간선을 분리해서 방향 그래프로 바꾸었습니다.

---

소스 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class B14284_간선이어가기2 {

    static int N,M;
    static int s,t;
    static int INF = 987654321;
    static int[] dist;
    static ArrayList<Node>[] list;
    static class Node implements Comparable<Node>{
        int v;
        int w;
        Node(int v, int w){
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Node o){
            return w-o.w;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        dist = new int[N+1];
        Arrays.fill(dist, INF);
        list = new ArrayList[N+1];
        for(int i = 0; i<N+1;i++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i<M;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int w = sc.nextInt();
            list[a].add(new Node(b, w));
            list[b].add(new Node(a,w));
        }
        s = sc.nextInt();
        t = sc.nextInt();
        dikstra(s);
        System.out.println(dist[t]);
    }

    static void dikstra(int st){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(st, 0));
        dist[st] = 0;

        while(!queue.isEmpty()){
            Node node = queue.poll();
            int v = node.v;
            int w = node.w;
            if(dist[v]<w) continue;
            for(int i = 0; i<list[v].size();i++){
                Node next = list[v].get(i);
                int v2 = next.v;
                int w2 = w+next.w;
                if(dist[v2]>w2){
                    dist[v2] = w2;
                    queue.add(new Node(v2, w2));
                }
            }
        }
    }
}