[JAVA/다익스트라] 백준 5719 거의 최단 경로

1. 문제

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

5719번: 거의 최단 경로

 

2. 풀이

1. 시작점에서 부터 다익스트라로 최단 경로를 구한다.
2. 도착점에서 부터 거슬러가며 최단 경로를 따로 표시한다. k[i][j] = 1; // i~j까지가 최단 경로면 1
3. 원래의 리스트에 간선 중 최단 경로가 아닌 간선만 추가해 리스트 갱신
4. 최단 경로를 뺀 간선으로만 다익스트라를 돌림

 

3. 코드

 

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

// 다익스트라

public class Main_5197 {
    
    static int n, m;
    static int s, d;
    static final int MAX = 500;
    static final int INF = 10000001;
    
    static class Node implements Comparable<Node>{
        int to, d;
        
        public Node(int t, int d) {
            this.to = t;
            this.d = d;
        }

        @Override
        public int compareTo(Node n) {
            return Integer.compare(this.d, n.d);
        }
        
    }
    
    static class Node2 { // from, to 저장
        int from, to, d;
        
        public Node2(int f, int t, int w) {
            from = f; to = t; d = w;
        }

    }
    
    public static void main(String[] args) throws Exception{
       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        List<Node>[] arr = new LinkedList[MAX+1]; // 순방향
        List<Node>[] arr2 = new LinkedList[MAX+1]; // 역방향
        
        Node2[] v = new Node2[10001]; // from, to 저장
        int[][] k = new int[MAX+1][MAX+1]; // 최단경로 저장
        
        for(int i = 0; i <= MAX; i++) {
            arr[i] = new LinkedList<>();
            arr2[i] = new LinkedList<>();
        }
        
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        int[] dist = new int[MAX+1];
        boolean[] visited = new boolean[MAX+1];
        Queue<Integer> q = new LinkedList<>();
        
        
        while(true) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            if(n == 0 && m == 0)
                break;
            
            for(int i = 0; i <= n; i++) {
                arr[i].clear();
                arr2[i].clear();
            }
            
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            
            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 c = Integer.parseInt(st.nextToken());
                
                arr[a].add(new Node(b,c));
                arr2[b].add(new Node(a,c));
                v[i] = new Node2(a, b, c);
            }

            
            Arrays.fill(dist, INF);
            
            pq.clear();
            pq.add(new Node(s, 0));
            dist[s] = 0;
            while(!pq.isEmpty()) {
                Node now = pq.poll();
                
                for(Node next: arr[now.to]) {
                    if(dist[next.to] > now.d + next.d) {
                        dist[next.to] = now.d + next.d;
                        pq.offer(new Node(next.to, dist[next.to]));
                    }
                }
            }
            
            if(dist[d] == INF) { // 최단 경로가 없는 경우
                sb.append("-1\n");
                continue;
            }
            
            // 최단경로 제외하고 경로 재설정
            dist[s] = 0;
            q.clear();
            q.add(d);
            for(int[] kk : k) 
                Arrays.fill(kk, 0);
            Arrays.fill(visited, false);
            while(!q.isEmpty()) {
                int node = q.poll();
                if(visited[node]) continue;
                visited[node] = true;
                for(Node next : arr2[node]) {
                    if(dist[next.to] + next.d == dist[node]) {
                        q.add(next.to);
                        k[next.to][node] = 1; // 최단 경로 저장
                    }
                }
            }
            
            for (int i = 0; i <= n; i++)
                arr[i].clear();
            
            for (int i = 0; i < m; i++) // 거의최단경로 저장
                if (k[v[i].from][v[i].to] == 0) // 최단 경로가 아니면
                    arr[v[i].from].add(new Node(v[i].to, v[i].d));
            
            // 다시 다익스트라 돌림
            pq.clear();
            pq.add(new Node(s, 0));
            Arrays.fill(dist, INF);
            while(!pq.isEmpty()) {
                Node now = pq.poll();
                for(Node next : arr[now.to]) {
                    if(dist[next.to] > now.d + next.d) {
                        dist[next.to] = now.d + next.d;
                        pq.add(new Node(next.to, dist[next.to]));
                    }
                }
            }
            
            if(dist[d] == INF) {
                sb.append("-1\n");
            }else {
                sb.append(String.valueOf(dist[d]) + "\n");
            }
        }
        System.out.println(sb.toString());
        
    }

}