Aizu Online Judge 0200 Traveling Alone: One-way Ticket of Youth

■0200 Traveling Alone: One-way Ticket of Youth

Warshall-Floyd．O(n³)でn=300なので，多分間に合うだろうという魂胆．

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[][] cost, time;  
17.  int n, m, k;  
18.   
19.  void run(){  
20.   for(;;){  
21.    n=sc.nextInt();  
22.    m=sc.nextInt();  
23.    if((n|m)==0){  
24.     break;  
25.    }  
26.    cost=new int[m][m];  
27.    time=new int[m][m];  
28.    for(int j=0; j<m; j++){  
29.     fill(cost[j], INF);  
30.     fill(time[j], INF);  
31.    }  
32.    for(int i=0; i<n; i++){  
33.     int a=sc.nextInt()-1;  
34.     int b=sc.nextInt()-1;  
35.     int c=sc.nextInt();  
36.     int t=sc.nextInt();  
37.     cost[a][b]=cost[b][a]=c;  
38.     time[a][b]=time[b][a]=t;  
39.    }  
40.    for(int k=0; k<m; k++){  
41.     for(int i=0; i<m; i++){  
42.      for(int j=0; j<m; j++){  
43.       cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);  
44.       time[i][j]=min(time[i][j], time[i][k]+time[k][j]);  
45.      }  
46.     }  
47.    }  
48.    k=sc.nextInt();  
49.    for(int i=0; i<k; i++){  
50.     int p=sc.nextInt()-1;  
51.     int q=sc.nextInt()-1;  
52.     int r=sc.nextInt();  
53.     if(r==0){  
54.      println(cost[p][q]+"");  
55.     }else{  
56.      println(time[p][q]+"");  
57.     }  
58.    }  
59.   }  
60.  }  
61.   
62.  void debug(Object... os){  
63.   System.err.println(Arrays.deepToString(os));  
64.  }  
65.   
66.  void print(String s){  
67.   System.out.print(s);  
68.  }  
69.   
70.  void println(String s){  
71.   System.out.println(s);  
72.  }  
73.   
74.  public static void main(String[] args){  
75.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
76.   new Main().run();  
77.  }  
78. }  

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[][] cost, time;
 int n, m, k;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   cost=new int[m][m];
   time=new int[m][m];
   for(int j=0; j<m; j++){
    fill(cost[j], INF);
    fill(time[j], INF);
   }
   for(int i=0; i<n; i++){
    int a=sc.nextInt()-1;
    int b=sc.nextInt()-1;
    int c=sc.nextInt();
    int t=sc.nextInt();
    cost[a][b]=cost[b][a]=c;
    time[a][b]=time[b][a]=t;
   }
   for(int k=0; k<m; k++){
    for(int i=0; i<m; i++){
     for(int j=0; j<m; j++){
      cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);
      time[i][j]=min(time[i][j], time[i][k]+time[k][j]);
     }
    }
   }
   k=sc.nextInt();
   for(int i=0; i<k; i++){
    int p=sc.nextInt()-1;
    int q=sc.nextInt()-1;
    int r=sc.nextInt();
    if(r==0){
     println(cost[p][q]+"");
    }else{
     println(time[p][q]+"");
    }
   }
  }
 }

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