Aizu Online Judge 1162 Discrete Speed

■1162 Discrete Speed

拡張ダイクストラ．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. // AC  
10. public class Main{  
11.   
12.  Scanner sc=new Scanner(System.in);  
13.   
14.  int INF=1<<28;  
15.  double EPS=1e-9;  
16.   
17.  int n, m;  
18.  int s, g;  
19.  LinkedList<E>[] es;  
20.   
21.  @SuppressWarnings("unchecked")  
22.  void run(){  
23.   for(;;){  
24.    n=sc.nextInt();  
25.    m=sc.nextInt();  
26.    if((n|m)==0){  
27.     break;  
28.    }  
29.    es=new LinkedList[n];  
30.    for(int i=0; i<n; i++){  
31.     es[i]=new LinkedList<E>();  
32.    }  
33.    s=sc.nextInt()-1;  
34.    g=sc.nextInt()-1;  
35.    for(int i=0; i<m; i++){  
36.     int x=sc.nextInt()-1;  
37.     int y=sc.nextInt()-1;  
38.     int d=sc.nextInt();  
39.     int c=sc.nextInt();  
40.     es[x].add(new E(y, d, c));  
41.     es[y].add(new E(x, d, c));  
42.    }  
43.    solve();  
44.   }  
45.  }  
46.   
47.  void solve(){  
48.   // [前][今][前から今の速度]  
49.   double[][][] d=new double[n][n][40];  
50.   PriorityQueue<P> que=new PriorityQueue<P>();  
51.   for(int j=0; j<n; j++){  
52.    for(int i=0; i<n; i++){  
53.     fill(d[j][i], INF);  
54.    }  
55.   }  
56.   d[s][s][1]=0;  
57.   que.offer(new P(s, s, 0, 0));  
58.   for(; !que.isEmpty();){  
59.    P p=que.poll();  
60.    if(d[p.q][p.p][p.v]+EPS<p.d){  
61.     continue;  
62.    }  
63.    for(E e : es[p.p]){  
64.     if(p.q==e.to){  
65.      continue;  
66.     }  
67.     for(int i=-1; i<=1; i++){  
68.      if(p.v+i<=0||p.v+i>e.c){  
69.       continue;  
70.      }  
71.      if(d[p.p][e.to][p.v+i]>p.d+(double)e.d/(p.v+i)+EPS){  
72.       d[p.p][e.to][p.v+i]=p.d+(double)e.d/(p.v+i);  
73.       que.offer(new P(p.p, e.to, p.v+i, d[p.p][e.to][p.v+i]));  
74.      }  
75.     }  
76.    }  
77.   }  
78.   double min=INF;  
79.   for(int i=0; i<n; i++){  
80.    min=min(min, d[i][g][1]);  
81.   }  
82.   println(""+(min<INF/2?min:"unreachable"));  
83.  }  
84.   
85.  class E{  
86.   int to, d, c;  
87.   
88.   E(int to, int d, int c){  
89.    this.to=to;  
90.    this.d=d;  
91.    this.c=c;  
92.   }  
93.  }  
94.   
95.  class P implements Comparable<P>{  
96.   int q, p, v;  
97.   double d;  
98.   
99.   P(int q, int p, int v, double d){  
100.    this.q=q;  
101.    this.p=p;  
102.    this.v=v;  
103.    this.d=d;  
104.   }  
105.   
106.   @Override  
107.   public int compareTo(P p){  
108.    if(d+EPS<p.d){  
109.     return -1;  
110.    }else if(d>p.d+EPS){  
111.     return 1;  
112.    }else{  
113.     return 0;  
114.    }  
115.   }  
116.   
117.  }  
118.   
119.  void debug(Object... os){  
120.   System.err.println(Arrays.deepToString(os));  
121.  }  
122.   
123.  void print(String s){  
124.   System.out.print(s);  
125.  }  
126.   
127.  void println(String s){  
128.   System.out.println(s);  
129.  }  
130.   
131.  public static void main(String[] args){  
132.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
133.   new Main().run();  
134.  }  
135. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, m;
 int s, g;
 LinkedList<E>[] es;

 @SuppressWarnings("unchecked")
 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   es=new LinkedList[n];
   for(int i=0; i<n; i++){
    es[i]=new LinkedList<E>();
   }
   s=sc.nextInt()-1;
   g=sc.nextInt()-1;
   for(int i=0; i<m; i++){
    int x=sc.nextInt()-1;
    int y=sc.nextInt()-1;
    int d=sc.nextInt();
    int c=sc.nextInt();
    es[x].add(new E(y, d, c));
    es[y].add(new E(x, d, c));
   }
   solve();
  }
 }

 void solve(){
  // [前][今][前から今の速度]
  double[][][] d=new double[n][n][40];
  PriorityQueue<P> que=new PriorityQueue<P>();
  for(int j=0; j<n; j++){
   for(int i=0; i<n; i++){
    fill(d[j][i], INF);
   }
  }
  d[s][s][1]=0;
  que.offer(new P(s, s, 0, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.q][p.p][p.v]+EPS<p.d){
    continue;
   }
   for(E e : es[p.p]){
    if(p.q==e.to){
     continue;
    }
    for(int i=-1; i<=1; i++){
     if(p.v+i<=0||p.v+i>e.c){
      continue;
     }
     if(d[p.p][e.to][p.v+i]>p.d+(double)e.d/(p.v+i)+EPS){
      d[p.p][e.to][p.v+i]=p.d+(double)e.d/(p.v+i);
      que.offer(new P(p.p, e.to, p.v+i, d[p.p][e.to][p.v+i]));
     }
    }
   }
  }
  double min=INF;
  for(int i=0; i<n; i++){
   min=min(min, d[i][g][1]);
  }
  println(""+(min<INF/2?min:"unreachable"));
 }

 class E{
  int to, d, c;

  E(int to, int d, int c){
   this.to=to;
   this.d=d;
   this.c=c;
  }
 }

 class P implements Comparable<P>{
  int q, p, v;
  double d;

  P(int q, int p, int v, double d){
   this.q=q;
   this.p=p;
   this.v=v;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   if(d+EPS<p.d){
    return -1;
   }else if(d>p.d+EPS){
    return 1;
   }else{
    return 0;
   }
  }

 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}