[백준] 2307번 도로검문

문제 설명

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

문제 풀이

• 다익스트라 알고리즘을 반복해서 수행하면 된다.
• 우선 1 -> N까지 최단 경로를 구한 후, 주어진 edge들을 하나씩 소거하면서 최단 경로를 구해준 후 최대 지연 시간을 구하면 된다.

소스 코드 (JAVA)

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

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static class Point implements Comparable<Point>{
        int n, d;

        public Point(int n, int d) {
            this.n = n;
            this.d = d;
        }

        @Override
        public int compareTo(Point o) {
            return this.d - o.d;
        }
    }

    static int N, M, INF = 987654321;
    static List<List<Point>> map = new ArrayList<>();
    static List<Point> edge = new ArrayList<>();
    static int solve() {
        PriorityQueue<Point> q = new PriorityQueue<>();
        int[] dist = new int[N+1];
        int result = 0;  //최대 지연 시간
        int minDist = 0;
        boolean first = true;
        // 도로 하나씩을 통제한다.
        for (Point e : edge) {
            q.clear();
            Arrays.fill(dist, INF);
            int from = e.n;
            int to = e.d;

            q.add(new Point(1, 0));
            dist[1] = 0;
            while(!q.isEmpty()) {
                Point cur = q.poll();
                if (cur.d > dist[cur.n]) continue;
                for (int i = 0; i < map.get(cur.n).size(); i++) {
                    int nNode = map.get(cur.n).get(i).n;
                    int nDist = cur.d + map.get(cur.n).get(i).d;
                    if ((cur.n == from && nNode == to) || (cur.n == to && nNode == from))
                        nDist = INF;
                    if (nDist < dist[nNode]) {
                        dist[nNode] = nDist;
                        q.add(new Point(nNode, nDist));
                    }
                }
            }
            if (first) {
                minDist = dist[N];
                first = false;
            } else
                result = Math.max(result, dist[N]);
        }
        if (result == INF) return -1;
        else return result - minDist;
    }

    static void input() throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i <= N; i++)
            map.add(new ArrayList<>());
        edge.add(new Point(0, 0));
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            map.get(a).add(new Point(b, d));
            map.get(b).add(new Point(a, d));
            edge.add(new Point(a, b));
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        bw.write(solve() + "\n");
        bw.flush();
    }
}