백준 14548 - The fastest road to banikoara

문제

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

리뷰

다익스트라를 통해 풀이할 수 있는 간단한 문제였다.

다익스트라에 사용되는 dist 배열의 크기를 주어질 수 있는 최대 데이터셋의 개수(N=500)의 2배인 1000으로 설정하여 들어올 수 있는 최대 도시 개수와 인덱스 개수를 맞추어 주었다.

이후 저장한 간선 정보를 바탕으로 A를 시작점으로 다익스트라를 돌려 B까지의
최단 거리를 구한뒤 저장해둔 start, end 정보와 함께 출력해주는 형식으로
로직을 구성하였다.

로직의 시간복잡도는 다익스트라의 $O(ElogV)$로 수렴하는데 $N=500$일 때 최대이므로
가능한 $V$, $E$의 최대값은 $1000$이다. 따라서 제한 조건 2초를 무난히 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static long[] dist = new long[1000];
    static List<List<Node>> graph = new ArrayList<>();
    static HashMap<String, Integer> cityMap = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = parseInt(br.readLine());
        int N, A, B, idx, w;
        int idx1, idx2;
        String start, end, city1, city2;

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        while (T-- > 0) {
            idx = 0;

            st = new StringTokenizer(br.readLine());
            N = parseInt(st.nextToken());

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

            start = st.nextToken();
            end = st.nextToken();

            A = idx;
            cityMap.put(start, idx++);
            B = idx;
            cityMap.put(end, idx++);

            while (N-- > 0) {
                st = new StringTokenizer(br.readLine());
                city1 = st.nextToken();
                if (cityMap.get(city1) == null)
                    cityMap.put(city1, idx++);
                city2 = st.nextToken();
                if (cityMap.get(city2) == null)
                    cityMap.put(city2, idx++);

                w = parseInt(st.nextToken());

                idx1 = cityMap.get(city1);
                idx2 = cityMap.get(city2);

                graph.get(idx1).add(new Node(idx2, w));
                graph.get(idx2).add(new Node(idx1, w));
            }

            sb.append(start).append(" ").append(end)
                    .append(" ").append(dijkstra(A, B)).append("\n");

            graph.clear();
            cityMap.clear();
        }

        System.out.println(sb);
        br.close();
    }


    static long dijkstra(int A, int B) {
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[A] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(n -> n.w));
        pq.offer(new Node(A, dist[A]));

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

            if (cur.n == B) return cur.w;

            if (dist[cur.n] < cur.w) continue;

            for (Node next : graph.get(cur.n)) {
                if (dist[next.n] < dist[cur.n] + next.w) continue;

                dist[next.n] = dist[cur.n] + next.w;
                pq.offer(new Node(next.n, dist[next.n]));
            }
        }

        return -1;
    }

    static class Node {
        int n;
        long w;

        public Node(int n, long w) {
            this.n = n;
            this.w = w;
        }
    }
}

결과