2686 Traveling by Stagecoach

「2686 Traveling by Stagecoach」の編集履歴（バックアップ）一覧はこちら

「2686 Traveling by Stagecoach」(2006/05/14 (日) 00:52:05) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2686 Traveling by Stagecoach
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             int n = sc.nextInt();
             int m = sc.nextInt();
             int p = sc.nextInt();
             int a = sc.nextInt()-1;
             int b = sc.nextInt()-1;
             if(n==0 && m==0 && p==0) break;
             int[] t = new int[n];
             for(int i=0;i<n;i++) t[i] = sc.nextInt();
             double[][] path = new double[m][m];
             for(int i=0;i<m;i++) Arrays.fill(path[i], Double.MAX_VALUE);
             for(int i=0;i<p;i++){
                 int x = sc.nextInt()-1;
                 int y = sc.nextInt()-1;
                 double z = sc.nextDouble();
                 path[x][y] = z;
                 path[y][x] = z;
             }
             
             Solver sol = new Solver(n, m, a, b, t, path);
             double ans = sol.solve();
             if(ans==Double.MAX_VALUE) System.out.println("Impossible");
             else System.out.printf("%.3f\r\n", sol.solve());
         }
     }
 }
 
 class Solver{
     int n;
     int m;
     int a;
     int b;
     int[] t;
     double[][] path;
     public Solver(int n, int m, int a, int b, int[] t, double[][] path) {
         this.n = n;
         this.m = m;
         this.a = a;
         this.b = b;
         this.t = t;
         this.path = path;
     }
     public double solve(){        
         boolean searched[][] = new boolean[m][1<<n];
         double x[][] = new double[m][1<<n];
         
         for(int i=0;i<m;i++) Arrays.fill(searched[i], false);
         for(int i=0;i<m;i++) Arrays.fill(x[i], Double.MAX_VALUE);
         x[a][(1<<n)-1] = 0;
         
         PriorityQueue<State> q = new PriorityQueue<State>();
         q.add(new State(a, (1<<n)-1, 0.0));
         while(!q.isEmpty()){
             State s = q.poll();
             if(searched[s.city][s.ticketcode]) continue;
             searched[s.city][s.ticketcode] = true;
             
             // end
             if(s.city==b){
                 return s.x;
             }
             
             // next
             TICKET: for(int i=0;i<n;i++){
                 if(!hasTicket(s.ticketcode, i)) continue TICKET;
                 int newcode = useTicket(s.ticketcode, i);
                 CITY: for(int j=0;j<m;j++){
                     if(path[s.city][j]==Double.MAX_VALUE) continue CITY;
                     if(searched[j][newcode]) continue CITY;
 
                     if(s.x + path[s.city][j]/t[i] < x[j][newcode]){
                         x[j][newcode] = s.x + path[s.city][j]/t[i];
                         q.add(new State(j, newcode, x[j][newcode]));                        
                     }
                 }
             }
         }
         return Double.MAX_VALUE;
     }
     private static boolean hasTicket(int ticketcode, int i){
         return (ticketcode>>i)%2==1;
     }
     private int useTicket(int ticketcode, int i){
         return ticketcode - (1<<i);
     }
 }
 
 class State implements Comparable<State>{
     int city;
     int ticketcode;
     double x;
     public State(int city, int ticketcode, double x) {
         this.city = city;
         this.ticketcode = ticketcode;
         this.x = x;
     }
     public int compareTo(State s){
         if(x>s.x) return 1;
         else if(x<s.x) return -1;
         else return 0;
     }
 }