14284 - 간선 이어가기 2[G5]

문제

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

 

정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.

s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.

 

풀이

기본적인 다익스트라 연습용 문제.

드디어 본격적으로 그래프 문제에 사용되는 Node와 Edge, 그리고 PQ 사용에 익숙해졌다.

작년 이후로 오랜만에 그래프가 두렵지 않았다.

코드

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<Node> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new Node(i));

        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 c = Integer.parseInt(st.nextToken());

            graph.get(a).edges.add(new Edge(b, c));
            graph.get(b).edges.add(new Edge(a, c));
        }

        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken()) - 1;
        int t = Integer.parseInt(st.nextToken()) - 1;
        graph.get(s).dist = 0; //출발 위치

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(graph.get(s));

        while (!pq.isEmpty()) {
            Node nowNode = pq.poll();

            if (nowNode.dist > graph.get(nowNode.no).dist) continue; //최단거리 이미 갱신되었음

            for (Edge edge : nowNode.edges) {
                long nowDist = nowNode.dist + edge.weight;
                Node nextNode = graph.get(edge.dest);
                if(nextNode.dist > nowDist) {
                    nextNode.dist = nowDist;
                    pq.add(nextNode);
                }
            }
        }

        System.out.println(graph.get(t).dist);
    }

}
class Node implements Comparable<Node> {
    long dist = Long.MAX_VALUE;
    int no;
    List<Edge> edges = new ArrayList<>();

    public Node(int no) {
        this.no = no;
    }

    @Override
    public int compareTo(Node n) {
        return Long.compare(this.dist, n.dist);
    }
}

class Edge {
    int dest;
    int weight;

    public Edge(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
    }
}