AOJ 2151: Brave Princess Revisited

問題リンク : Brave Princess Revisited | Aizu Online Judge

問題概要 : 本文を参照してもらいたい。。。

使用した言語 : Java

解法 :
int used[今いる宿][今もってるお金] := 襲われた数の最小　として Dijkstraしました。　
護衛を雇えるなら雇った場合と雇わない場合をキューに入れていきました。

困ったこと :

1. listで２次配列を作る際にWarningが出まくった
原因と解決策 : @SuppressWarnings("unchecked")というものをつけた。これをつけると""で囲んだ警告を無視してくれるそうな。。。

2. java.lang.ClassCastExceptionが出まくった
原因と解決策 : 自作のクラスでプライオリティキューを使っていたが、その順位付けの基準を実装していなかった。自作のクラスを使用する場合には Comparableを implements しないといけないみたいだ。

コメント：
Javaを本格的につかいはじめてまだ２週間なのでJavaの仕様で苦労した。下記のコードでは15.16秒という驚異的なタイムをたたき出してしまった。Javaに詳しくなってから原因を探してみようとおもう。

コード :

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main{
 
    private static int[][] used;
    private static int N,M,L;
    private static List<Pox>[] list;
    private static final int INF = 100000000;
 
    private static class Pox{
    public int B,D,E;
    Pox(){
        B = D = E = 0;
    }
 
    Pox(int b,int d,int e){
        B = b;
        D = d;
        E = e;
    }
    }
 
    private static class Eleac implements Comparable<Eleac>{
    public int id,L,num;
 
    Eleac(){
        id = L = num = 0;
    }
 
    Eleac(int a,int b,int c){
        id = a;
        L = b;
        num = c;
    }
 
    @Override
    public int compareTo(Eleac a){
        return 1;
    }
 
    }
 
     @SuppressWarnings("unchecked")
      public static void main(String args[])throws IOException{
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
       
      while(true)
          {
          String[] elements = in.readLine().split(" ");
          N = Integer.parseInt(elements[0]);
          M = Integer.parseInt(elements[1]);
          L = Integer.parseInt(elements[2]);
          if(N == 0 && M == 0 && L == 0)
              break;
 
           
 
          used = new int[N+1][L+1];
          list = new ArrayList[N+2];
 
          for(int i=0;i<N+1;i++)
              for(int j=0;j<L+1;j++)
              used[i][j] = INF;
 
          for(int i=0;i<N+1;i++)
              list[i] = new ArrayList<Pox>();
           
          for(int i=0;i<M;i++)
              {
             elements = in.readLine().split(" ");
             int A,B,D,E;
              A = Integer.parseInt(elements[0]);
              B = Integer.parseInt(elements[1]);
              D = Integer.parseInt(elements[2]);
              E = Integer.parseInt(elements[3]);
 
              list[A].add(new Pox(B,D,E));  
              list[B].add(new Pox(A,D,E));
              }
 
          Queue<Eleac> que = new PriorityQueue<Eleac>();
 
          que.offer(new Eleac(1,L,0)); //Eleac(id,money,the number of eemy)
          used[1][L] = 0;       
 
          int men = INF;
          while(que.size() > 0)
              {
              Eleac p = que.poll(); 
              int now = p.id;
              int money = p.L;
              int val = p.num;
               
              if(now == N)
                  {
                  used[now][money] = Math.min(used[now][money],val);    
                  continue;
                  }
               
              
              for(int i=0;i<list[now].size();i++)
                  {
                  int need = list[now].get(i).D;
 
                  int new_pos = list[now].get(i).B;
                  int the_number = list[now].get(i).E;
                   
                  if(money-need >= 0 && used[new_pos][money-need] > val)
                      {
                      used[new_pos][money-need] = val;
                      que.add(new Eleac(new_pos,money-need,val));
                      }                 
                  if(used[new_pos][money] > val+the_number)
                      {
                      used[new_pos][money] = val+the_number;
                      que.add(new Eleac(new_pos,money,val+the_number));
                      }
 
                  }
 
               
              }
 
          for(int i=0;i<=L;i++)
              {
              men = Math.min(men,used[N][i]);
              }
          System.out.println(men);
          }
      }
 
}