Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.PriorityQueue;
- import java.util.Scanner;
- public class hello8 {
- public static void main(String[] args){
- Scanner input = new Scanner(System.in);
- while(true){
- int numberOfCity = input.nextInt();
- int path = input.nextInt();
- if(numberOfCity == 0 && path ==0 ){
- //System.out.println("FFF");
- break;
- }
- int from = input.nextInt();
- int to = input.nextInt();
- if(!(numberOfCity == 0 && path ==0) ){
- int people = input.nextInt();
- Vertex[] v = new Vertex[numberOfCity+1];
- for(int i = 1 ; i < v.length ; i++){
- int name = input.nextInt();
- v[name] = new Vertex(name , input.nextInt());
- }
- int[][] weightMatrix = new int[numberOfCity+1][numberOfCity+1];
- for(int i = 0 ; i < path ; i++){
- int tempfrom = input.nextInt();
- int tempto = input.nextInt();
- weightMatrix[tempfrom][tempto] = v[tempto].getWeight();
- weightMatrix[tempto][tempfrom] = v[tempfrom].getWeight();
- }
- //for(int i = 1 ; i <weightMatrix.length ; i++){
- //for(int j = 1 ; j <weightMatrix.length; j++){
- //System.out.print(weightMatrix[i][j] +" ");
- //}
- //System.out.println();
- //}
- for(int i = 1 ; i <weightMatrix.length ; i++){
- for(int j = 1 ; j <weightMatrix.length; j++){
- if(weightMatrix[i][j] == 0){
- weightMatrix[i][j] = Integer.MAX_VALUE;
- }
- }
- }
- v[from].minDistance = Integer.MAX_VALUE;
- PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
- vertexQueue.add(v[from]);
- boolean[] isEnter = new boolean[numberOfCity +1];
- while (!vertexQueue.isEmpty()) {
- Vertex u = vertexQueue.poll();
- isEnter[u.getName()] = true;
- for (int i = 1 ;i <numberOfCity +1 ; i++ ){
- if(isEnter [i] == false && weightMatrix[u.getName()][i] != Integer.MAX_VALUE){
- Vertex goal = v[i];
- int weight = weightMatrix[u.getName()][i];
- int compare = 0;
- if( weight < u.minDistance){
- compare = weight;
- }
- else{
- compare = u.minDistance;
- }
- if(compare>= goal.minDistance){
- vertexQueue.remove(goal);
- goal.minDistance = compare ;
- vertexQueue.add(goal);
- }
- }
- }
- }
- //System.out.println(v[to].minDistance);
- if(people % (v[to].minDistance-1) != 0){
- System.out.println(people / (v[to].minDistance-1) +1 +" is the minimum number of trips.");
- }
- else{
- System.out.println(people / (v[to].minDistance-1) + " is the minimum number of trips.");
- }
- }
- }
- }
- }
- class Vertex implements Comparable<Vertex>{
- int weight ;
- int name;
- int minDistance =0;
- public Vertex(int name , int weight){
- this.weight = weight;
- this.name = name;
- }
- public int getName(){
- return name;
- }
- public int getWeight(){
- return weight;
- }
- @Override
- public int compareTo(Vertex other) {
- // TODO Auto-generated method stub
- return Double.compare(other.minDistance , minDistance);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement