[BOJ] 백준 [2307] 도로검문 JAVA

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

2307번: 도로검문

[문제]

[풀이]

1. 다익스트라를 돌려서 N번 노드까지의 최단거리를 구하고 , 경로를 구한다.
2. 구한 경로의 edge를 하나씩 빼면서 다익스트라를 경로의 수 만큼 다시 돌린다.
3. 늘어난 시간 중 가장 긴 거리와 1번에서 구한 최단거리의 차이를 반환하면 끝.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static int N,M;
    static ArrayList<int[]>[] list;
    static int[] distance,path;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        N = input[0]; M = input[1];
        init();
        for(int i=0;i<M;i++){
            input = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            list[input[0]].add(new int[]{input[1], input[2]});
            list[input[1]].add(new int[]{input[0], input[2]});
        }
 
        path = new int[N+1];
        Arrays.fill(path,-1);
 
        int shortPath = findShortestPath();
        int maxPath = 0;
        for(int i=N;i>0;i=path[i])
            maxPath = Math.max(maxPath,otherPath(path[i],i));
 
        if(maxPath==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(maxPath-shortPath);
 
 
    }
 
    private static int findShortestPath() {
 
        Arrays.fill(distance,Integer.MAX_VALUE);
        distance[1]=0;
        Queue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]);
        q.add(new int[]{1, 0});
        while (!q.isEmpty()){
            int[] cur = q.poll();
            if(cur[1] > distance[cur[0]]) continue;
 
            for (int[] next : list[cur[0]]) {
 
                if(distance[next[0]] > distance[cur[0]]+next[1]){
                    distance[next[0]] = distance[cur[0]]+next[1];
                    q.add(new int[]{next[0],distance[next[0]]});
                    path[next[0]] = cur[0];
                }
            }
        }
        return distance[N];
    }
 
    private static int otherPath(int from,int to) {
        Arrays.fill(distance,Integer.MAX_VALUE);
        distance[1]=0;
        Queue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]);
        q.add(new int[]{1, 0});
        while (!q.isEmpty()){
            int[] cur = q.poll();
            if(cur[1] > distance[cur[0]]) continue;
 
            for (int[] next : list[cur[0]]) {
                if(from == cur[0] && to==next[0]) continue;
                if(distance[next[0]] > distance[cur[0]]+next[1]){
                    distance[next[0]] = distance[cur[0]]+next[1];
                    q.add(new int[]{next[0],distance[next[0]]});
                }
            }
        }
        return distance[N];
    }
 
    private static void init() {
        list = new ArrayList[N+1];
        for(int i=1;i<=N;i++) list[i]= new ArrayList<>();
        distance = new int[N+1];
    }
}