どのようにこのアルゴリズムを解決するために一度だけbfsを使用するのですか？</p> <p>ラビリンスは、m個のパスで接続されたn個の部屋で構成されています

Question

問題は、訪問https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4474問題は概ね以下のように記載されて

uva1599あります。各パスはいくつかのカラーCIに色分けされています。部屋番号1から部屋番号nまでの までの理想的なパスを探します。その色配列は、最短パスのうち辞書最小である場合、パスは、理想的な経路である。（2 < = N = 100000 <、1 < = M < = 200000、< = C < 1 = 10^9）

I各部屋の最短経路を得るために最終室のbfsを使用することができ、同じ長さの経路と異なる色を持つ複数の経路がある場合には、最初からbfsを使用して検索することができます。

この問題を1つのbfsだけで解決する方法はありますか？

私は最後の部屋から、各部屋の最短経路とカラーシーケンスを取得するbfsを使用して開始しようとしています。アイダエルパスは部屋1のカラーシーケンスに格納されます。

そうですか？

ありがとうございました。

Answer 1

これは私のコードです。エラーはランタイムエラーです

import java.util.*; 
import java.util.concurrent.LinkedBlockingQueue; 

public class IdealPath { 
    //store the path between two rooms, if there is a path between room i and j, then graph[i][j] = 1 
    public static int [][]graph; 
    //store the color between two rooms 
    public static int [][]color; 
    //store the shortest path to the end room for each room 
    public static int []distance; 
    //store the ideal color sequence for each room 
    public static String []color_seq; 
    //use for bfs 
    public static Queue<Integer> queue = new LinkedBlockingQueue<Integer>(); 

    /** 
    * Initialize parameters 
    * @param n 
    */ 
    public static void init(int n){ 
     graph = new int[n][n]; 
     color = new int[n][n]; 
     distance = new int[n]; 
     color_seq = new String[n]; 
     queue.clear(); 
    } 

    /** 
    * use bfs to find the ideal path 
    * @param n 
    */ 
    public static void bfs(int n){ 
     //init the end room 
     distance[n-1] = 0; 
     color_seq[n-1] = ""; 
     queue.add(n-1); 
     //loop until the queue is empty 
     while(!queue.isEmpty()){ 
      int node = queue.poll(); 
      for (int i = 0; i < n; i++) { 
       //there is a path 
       if (graph[node][i] == 1){ 
        //the room is not visited or is visited by the last floor 
        if (distance[i] == 0 || distance[i] == distance[node] + 1) { 
         distance[i] = distance[node] + 1; //add the distance 
         String str = color[i][node] + " " + color_seq[node]; //generate the color sequence 
         if (color_seq[i] == null) 
          color_seq[i] = str.trim(); 
         //choose the ideal color sequence for the room 
         else 
          color_seq[i] = compare(color_seq[i], str) ? str.trim() : color_seq[i].trim(); 
         queue.add(i); 
        } 
       } 
      } 
     } 
    } 

    /** 
    * return true if str2 < str1 
    * @param str1 
    * @param str2 
    * @return 
    */ 
    public static boolean compare(String str1, String str2){ 
     String []arr2 = str2.trim().split(" "); 
     String []arr1 = str1.trim().split(" "); 
     //assume the lengths of arr1 and arr2 are same 
     for (int i = 0; i < arr1.length; i++) { 
      if (arr2[i].compareTo(arr1[i]) < 0) 
       return true; 
     } 
     return false; 
    } 

    public static void main(String []args){ 
     Scanner input = new Scanner(System.in); 
     while(input.hasNext()){ 
      //input 
      int n = input.nextInt(); 
      int m = input.nextInt(); 
      init(n); 
      for (int i = 0; i < m; i++) { 
       int node1 = input.nextInt() - 1; 
       int node2 = input.nextInt() - 1; 
       //ignore the path to itself 
       if (node1 != node2) { 
        graph[node1][node2] = graph[node2][node1] = 1; 
        int c = input.nextInt(); 
        //choose the smallest path if it has multi path 
        color[node1][node2] = color[node2][node1] = (color[node1][node2] == 0) ? c : Math.min(c, color[node1][node2]); 
       } 
      } 
      //use bfs to find the ideal path 
      bfs(n); 
      //output 
      //the ideal path is stored in the color_seq[0] 
      String res = color_seq[0].trim(); 
      System.out.println((res.length() + 1)/2); 
      System.out.println(res); 
     } 
    } 
}