Aizu Online Judge 0212 Highway Express Bus

■0212 Highway Express Bus

拡張Dijkstra．ノードを(今いる町, 残りチケット枚数)とする．後は次状態に遷移する際に，チケットを使った場合と使わなかった場合で更新．

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. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int c, n, m, s, g;  
17.  LinkedList<E>[] es;  
18.   
19.  @SuppressWarnings("unchecked")  
20.  void run(){  
21.   for(;;){  
22.    c=sc.nextInt();  
23.    n=sc.nextInt();  
24.    m=sc.nextInt();  
25.    s=sc.nextInt()-1;  
26.    g=sc.nextInt()-1;  
27.    if((c|n|m|(s+1)|(g+1))==0){  
28.     break;  
29.    }  
30.    es=new LinkedList[n];  
31.    for(int i=0; i<n; i++){  
32.     es[i]=new LinkedList<E>();  
33.    }  
34.    for(int i=0; i<m; i++){  
35.     int u=sc.nextInt()-1;  
36.     int v=sc.nextInt()-1;  
37.     int w=sc.nextInt()/10;  
38.     es[u].add(new E(v, w));  
39.     es[v].add(new E(u, w));  
40.    }  
41.    solve();  
42.   }  
43.  }  
44.   
45.  void solve(){  
46.   int[][] d=new int[n][c+1];  
47.   PriorityQueue<P> que=new PriorityQueue<P>();  
48.   
49.   for(int i=0; i<n; i++){  
50.    Arrays.fill(d[i], INF);  
51.   }  
52.   d[s][c]=0;  
53.   que.offer(new P(s, c, 0));  
54.   for(; !que.isEmpty();){  
55.    P p=que.poll();  
56.    if(d[p.v][p.c]<p.d){  
57.     continue;  
58.    }  
59.    for(E e : es[p.v]){  
60.     if(d[e.to][p.c]>d[p.v][p.c]+e.cost){  
61.      d[e.to][p.c]=d[p.v][p.c]+e.cost;  
62.      que.offer(new P(e.to, p.c, d[e.to][p.c]));  
63.     }  
64.     if(p.c>0&&d[e.to][p.c-1]>d[p.v][p.c]+e.cost/2){  
65.      d[e.to][p.c-1]=d[p.v][p.c]+e.cost/2;  
66.      que.offer(new P(e.to, p.c-1, d[e.to][p.c-1]));  
67.     }  
68.    }  
69.   }  
70.   int min=INF;  
71.   for(int i=0; i<=c; i++){  
72.    min=min(min, d[g][i]);  
73.   }  
74.   min*=10;  
75.   println(""+min);  
76.  }  
77.   
78.  class E{  
79.   int to, cost;  
80.   
81.   E(int to, int cost){  
82.    this.to=to;  
83.    this.cost=cost;  
84.   }  
85.  }  
86.   
87.  class P implements Comparable<P>{  
88.   int v, c, d;  
89.   
90.   P(int v, int c, int d){  
91.    this.v=v;  
92.    this.c=c;  
93.    this.d=d;  
94.   }  
95.   
96.   @Override  
97.   public int compareTo(P p){  
98.    return d-p.d;  
99.   }  
100.  }  
101.   
102.  void debug(Object... os){  
103.   System.err.println(Arrays.deepToString(os));  
104.  }  
105.   
106.  void print(String s){  
107.   System.out.print(s);  
108.  }  
109.   
110.  void println(String s){  
111.   System.out.println(s);  
112.  }  
113.   
114.  public static void main(String[] args){  
115.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
116.   new Main().run();  
117.  }  
118. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

 void solve(){
  int[][] d=new int[n][c+1];
  PriorityQueue<P> que=new PriorityQueue<P>();

  for(int i=0; i<n; i++){
   Arrays.fill(d[i], INF);
  }
  d[s][c]=0;
  que.offer(new P(s, c, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v][p.c]<p.d){
    continue;
   }
   for(E e : es[p.v]){
    if(d[e.to][p.c]>d[p.v][p.c]+e.cost){
     d[e.to][p.c]=d[p.v][p.c]+e.cost;
     que.offer(new P(e.to, p.c, d[e.to][p.c]));
    }
    if(p.c>0&&d[e.to][p.c-1]>d[p.v][p.c]+e.cost/2){
     d[e.to][p.c-1]=d[p.v][p.c]+e.cost/2;
     que.offer(new P(e.to, p.c-1, d[e.to][p.c-1]));
    }
   }
  }
  int min=INF;
  for(int i=0; i<=c; i++){
   min=min(min, d[g][i]);
  }
  min*=10;
  println(""+min);
 }

 class E{
  int to, cost;

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

 class P implements Comparable<P>{
  int v, c, d;

  P(int v, int c, int d){
   this.v=v;
   this.c=c;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

 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();
 }
}