[백준] 최단경로

참고 : www.acmicpc.net/problem/1753

1753번: 최단경로

 

- 다익스트라

- 기본 다익스트라 구현 문제와 같음. bfs + adj 리스트 구현 잘 생각할 것.

 

import java.util.*;

class Edge implements Comparable<Edge> {
    int vertex;
    int weight;
    public Edge(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }

    public int compareTo(Edge n) {
        return weight - n.weight;
    }
}

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();
        int K = sc.nextInt();
        int[] d = new int[V+1];
        Arrays.fill(d, 100_000_000);
        List<Edge>[] adj = new ArrayList[V+1];
        for (int i = 0; i < V+1; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            int V1 = sc.nextInt();
            int V2 = sc.nextInt();
            int weight = sc.nextInt();
            adj[V1].add(new Edge(V2, weight));
        }

        d[K] = 0; // K = start

        boolean[] visited = new boolean[V+1];
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
        pq.offer(new Edge(K , 0));
        while(!pq.isEmpty()) {
            Edge edge = pq.poll();

            if(visited[edge.vertex]) continue;
            visited[edge.vertex] = true;

            for(int i = 0; i< adj[edge.vertex].size(); i++) {
                Edge tmp = adj[edge.vertex].get(i);
                if(d[tmp.vertex] > d[edge.vertex] + tmp.weight) {
                    d[tmp.vertex] = d[edge.vertex] + tmp.weight;
                    pq.add(new Edge(tmp.vertex, d[tmp.vertex]));
                }
            }
        }

        for (int i = 1; i <= V; i++) {
            if (d[i] == 100_000_000) System.out.println("INF");
            else System.out.println(d[i]);
        }
    }
}