Advertisement
Guest User

Untitled

a guest
Oct 26th, 2014
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.24 KB | None | 0 0
  1.  
  2. import java.util.PriorityQueue;
  3. import java.util.Scanner;
  4.  
  5. public class hello8 {
  6.     public static void main(String[] args){
  7.         Scanner input = new Scanner(System.in);
  8.         while(true){
  9.             int numberOfCity = input.nextInt();
  10.             int path = input.nextInt();
  11.             if(numberOfCity == 0 && path ==0 ){
  12.                 //System.out.println("FFF");
  13.                 break;
  14.             }
  15.             int from = input.nextInt();
  16.             int to = input.nextInt();
  17.  
  18.             if(!(numberOfCity == 0 && path ==0) ){
  19.                 int people = input.nextInt();
  20.                 Vertex[] v = new Vertex[numberOfCity+1];
  21.                 for(int i = 1 ; i < v.length ; i++){
  22.                     int name = input.nextInt();
  23.                     v[name] = new Vertex(name , input.nextInt());
  24.                 }
  25.                 int[][] weightMatrix = new int[numberOfCity+1][numberOfCity+1];
  26.                 for(int i = 0 ; i < path ; i++){
  27.                     int tempfrom = input.nextInt();
  28.                     int tempto = input.nextInt();
  29.                     weightMatrix[tempfrom][tempto] = v[tempto].getWeight();
  30.                     weightMatrix[tempto][tempfrom] = v[tempfrom].getWeight();
  31.                 }
  32.                
  33.                 //for(int i = 1 ; i <weightMatrix.length ; i++){
  34.                     //for(int j = 1 ; j <weightMatrix.length; j++){
  35.                         //System.out.print(weightMatrix[i][j] +" ");
  36.                     //}
  37.                     //System.out.println();
  38.                 //}
  39.                
  40.                 for(int i = 1 ; i <weightMatrix.length ; i++){
  41.                     for(int j = 1 ; j <weightMatrix.length; j++){
  42.                         if(weightMatrix[i][j] == 0){
  43.                             weightMatrix[i][j] = Integer.MAX_VALUE;
  44.                         }
  45.                     }
  46.                 }
  47.                
  48.                 v[from].minDistance = Integer.MAX_VALUE;
  49.                 PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
  50.                 vertexQueue.add(v[from]);
  51.                 boolean[] isEnter = new boolean[numberOfCity +1];
  52.                 while (!vertexQueue.isEmpty()) {
  53.                     Vertex u = vertexQueue.poll();
  54.                     isEnter[u.getName()] = true;
  55.                     for (int i = 1 ;i <numberOfCity +1 ; i++ ){
  56.                         if(isEnter [i] == false  && weightMatrix[u.getName()][i] != Integer.MAX_VALUE){
  57.                             Vertex goal = v[i];
  58.                             int weight =  weightMatrix[u.getName()][i];
  59.                             int compare = 0;
  60.  
  61.                             if( weight < u.minDistance){
  62.                                 compare = weight;
  63.                             }
  64.                             else{
  65.                                 compare = u.minDistance;
  66.                             }
  67.                             if(compare>= goal.minDistance){
  68.                                 vertexQueue.remove(goal);
  69.                                 goal.minDistance = compare ;      
  70.                                 vertexQueue.add(goal);                 
  71.                             }
  72.                         }
  73.                     }
  74.                 }
  75.                 //System.out.println(v[to].minDistance);
  76.                 if(people % (v[to].minDistance-1) != 0){
  77.                     System.out.println(people / (v[to].minDistance-1) +1  +" is the minimum number of trips.");
  78.                 }
  79.                 else{
  80.                     System.out.println(people / (v[to].minDistance-1) + " is the minimum number of trips.");
  81.                 }
  82.             }
  83.         }
  84.     }
  85. }
  86. class Vertex implements Comparable<Vertex>{
  87.     int weight ;
  88.     int name;
  89.     int minDistance =0;
  90.     public Vertex(int name , int weight){
  91.         this.weight = weight;
  92.         this.name = name;
  93.     }
  94.     public int getName(){
  95.         return name;
  96.     }
  97.     public int getWeight(){
  98.         return weight;
  99.     }
  100.     @Override
  101.     public int compareTo(Vertex other) {
  102.         // TODO Auto-generated method stub
  103.         return Double.compare(other.minDistance , minDistance);
  104.     }  
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement