<Algorithm> 76. 5719번 거의 최단경로

1. 5719번 거의 최단경로

• 최단경로가 아닌 경로들만 사용해서 최단경로를 만드는 문제

• 처음에 단순하게 다익스트라로 최단경로를 구하고 그 경로만 사용하지 못하게 해서 다시 다익스트라를 돌리면 될 것 같았다.

• 문제는 최단경로가 여러개 있을 때 중복경로가 존재 할 수 있다. 1->2 -> 4 ->5 일때 1 -> 2 -> 3 ->5 이렇게 최단경로가 될 수도 있다

• 75프로에서 틀리는데 수정이 필요하고 코드도 다익스트라를 너무 부르는 것 같아서 수정이 필요하다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTokenizer;   public class Main {          static int[] dist;     static int[] path;     static int total = 0;     static boolean[] visited;     static boolean[][] finalPath;     static boolean[][] ShortPath;     public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 ArrayList<Integer> ans = new ArrayList<>();         for(;;) {             StringTokenizer st = new StringTokenizer(br.readLine());             int N = Integer.parseInt(st.nextToken());             int M = Integer.parseInt(st.nextToken());             if(N==0 && M==0) break;             st = new StringTokenizer(br.readLine());                          int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());                          ArrayList<Edge>[] alist = new ArrayList[N];             dist = new int[N];             path = new int[N];             visited = new boolean[N];             ShortPath = new boolean[N][N];             finalPath = new boolean[N][N];                          for(int i = 0; i < N; i++) {                 alist[i] = new ArrayList<>();             }                          int arr[][] = new int [N][N];                          for(int i = 0; i < M ; i ++) {                 st = new StringTokenizer(br.readLine());                 int u = Integer.parseInt(st.nextToken());                 int v = Integer.parseInt(st.nextToken());                 int p = Integer.parseInt(st.nextToken());                 arr[u][v] = p;                                  alist[u].add(new Edge(v, p));             }                                      dijkstra(alist, a, false);             int temp_dist = dist[b];             int temp_b = b;                          for(;;) {                 if(path[b] == -1) break;                     ShortPath[path[b]][b] = true;                     if(b == temp_b) finalPath[path[b]][b] = true;                     b = path[b];             }             //System.out.println(Arrays.deepToString(finalPath));                          while(true) {                                  dist = new int[N];                 path = new int[N];                 visited = new boolean[N];                                 dijkstra(alist, a, false);                 //System.out.println(dist[temp_b]);                 if(temp_dist != dist[temp_b] || dist[temp_b]==Integer.MAX_VALUE && temp_dist != Integer.MAX_VALUE) {                     dist = new int[N];                     path = new int[N];                     visited = new boolean[N];                                     dijkstra(alist, a, true);                     break;                 } else {                     b = temp_b;                                          for(;;) {                         if(path[b] == -1) break;                         ShortPath[path[b]][b] = true;                         if(b == temp_b) finalPath[path[b]][b] = true;                         b = path[b];                     }                                     }             }             if(dist[temp_b] != Integer.MAX_VALUE) {                 ans.add(dist[temp_b]);             }else {                 ans.add(-1);             }         }                  for(Integer str : ans)             System.out.println(str);              }      public static void dijkstra(ArrayList<Edge>[] alists, int startVertex, boolean fin) {             PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {                 @Override                 public int compare(Edge o1, Edge o2) {                     // TODO Auto-generated method stub                     return o1.weight - o2.weight;                 }             });                          for(int i = 0; i < alists.length; i++) {                 dist[i] = Integer.MAX_VALUE;                 path[i] = -1;             }                          dist[startVertex] = 0;             path[startVertex] = -1;                          pq.add(new Edge(startVertex, 0));                          while(!pq.isEmpty()) {                 Edge edge = pq.poll();                 int vertex = edge.vertex;                                  if(visited[vertex]) continue;                                  visited[vertex] = true;                                  for(Edge e : alists[vertex]) {                     int layoverWeight = dist[vertex] + e.weight;                     int destination = e.vertex;                    if(dist[destination] > layoverWeight && !finalPath[vertex][destination]) {                       if(fin == true && ShortPath[vertex][destination]) continue;                          dist[destination] = layoverWeight;                        path[destination] = vertex;                        pq.add(new Edge(destination, dist[destination]));                    }                 }             }                      }              }   class Edge{         int vertex;         int weight;         public Edge(int vertex, int weight) {             super();             this.vertex = vertex;             this.weight = weight;         }     } Colored by Color Scripter

cs

참고 & 출처