백준 5972번 Java 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	MB	골드 5

---

풀이

 이 문제도 밀려있던 문제이다. 전형적인 최단거리 문제이다. 문제에서 사람 헷갈리라고 가는 길의 길이는 고려하지 않는다고 하지만, 간선 가중치를 여물의 양으로 따져야 하기에 결국은 최단거리 문제로 귀결된다. 우리가 잘 아는 다익스트라를 사용하도록 하자.

 

잘 쓰던 C++ 대신 자바를 쓴 이유는 당시에 컴퓨터에 깔려있는건 자바밖에 없었다 허허... 그래서 구현과 제출에 정말 애를 먹었던 기억이 있다.

코드

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

class Pair implements Comparable<Pair> {
    public int destination, distance;
    public Pair() { this(0,0); }
    public Pair(int destination, int distance) {
        this.destination = destination;
        this.distance = distance;
    }

    @Override
    public int compareTo(Pair p) {
        return this.distance == p.distance ?
                this.destination - p.destination :
                this.distance - p.distance;
    }
}

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int n, m;
    List<Pair>[] graph;

    public static void main(String[] args) throws IOException {
        (new Main()).solve();
    }

    public Main() throws IOException {
        int a, b, c;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new ArrayList[n + 1];

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

        for(int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            graph[a].add(new Pair(b, c));
            graph[b].add(new Pair(a, c));
        }
    }

    private int[] dijkstra() {
        int[] dist = new int[n + 1];
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>();

        for(int i = 0; i <= n; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        dist[1] = 0;
        pq.add(new Pair(1, 0));

        while(!pq.isEmpty()) {
            Pair cur = pq.poll();

            if (cur.distance > dist[cur.destination]) {
                continue;
            }

            for(Pair next : graph[cur.destination]) {
                if (dist[next.destination] > cur.distance + next.distance) {
                    pq.add(new Pair(next.destination, cur.distance + next.distance));
                    dist[next.destination] = cur.distance + next.distance;
                }
            }
        }
        return dist;
    }
    public void solve() {
        System.out.print(dijkstra()[n]);
    }
}