Guest User

Untitled

a guest
Nov 25th, 2017
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.21 KB | None | 0 0
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.BufferedWriter;
  4. import java.io.FileNotFoundException;
  5. import java.io.FileReader;
  6. import java.io.FileWriter;
  7. import java.io.IOException;
  8. import java.io.PrintWriter;
  9. import java.util.ArrayList;
  10. import java.util.Comparator;
  11. import java.util.PriorityQueue;
  12. import java.util.StringTokenizer;
  13. import java.util.logging.Level;
  14. import java.util.logging.Logger;
  15.  
  16. class Pair extends Solution implements Comparator<Pair>{
  17. public int first;
  18. public int second;
  19. public Pair(Integer rt, Integer pr) { this.first = rt; this.second = pr; }
  20. public Pair(){
  21. first=-1;
  22. second=-1;
  23. }
  24. public static boolean same(Integer first, Integer second) {
  25. return first == null ? second == null : first.equals(second);
  26. }
  27. Integer getFirst() { return first; }
  28. Integer getSecond() { return second; }
  29. void setFirst(Integer o) { first = o; }
  30. void setSecond(Integer o) { second = o; }
  31. public boolean equals(Pair obj) {
  32. if( ! (obj instanceof Pair))
  33. return false;
  34. Pair p = (Pair)obj;
  35. return same(p.first, this.first) && same(p.second, this.second);
  36. }
  37. public String toString() {
  38. return "Pair{"+first+", "+second+"}";
  39. }
  40. public int compare(Pair o1, Pair o2) {
  41. return o2.second-o1.second;
  42. }
  43. };
  44. class Four extends Solution implements Comparator<Four>{
  45. public int first;
  46. public double second;
  47. public int third;
  48. public int four;
  49. public Four(int f, double s,int t,int fo){
  50. first = f;
  51. second = s;
  52. third = t;
  53. four = fo;
  54. }
  55. public Four(){
  56. first=-1;
  57. second=-1.0;
  58. third=-1;
  59. four = -1;
  60. }
  61. public int compare(Four o1, Four o2) {
  62. return (int)o1.second-(int)o2.second;
  63. }
  64.  
  65. };
  66. public class Solution {
  67. public static ArrayList<ArrayList<ArrayList<Pair>>> matrix;
  68. public static int start;
  69. public static int finish;
  70. public static int num_of_cities;
  71. public static int num_of_roads;
  72. public static Pair nothing;
  73. public static void main(String arg[]) throws FileNotFoundException{
  74. matrix = new ArrayList< ArrayList< ArrayList< Pair >>>();
  75. nothing = new Pair(-1,-1);
  76. BufferedReader in = new BufferedReader(new FileReader("input.txt"));
  77. try{
  78. num_of_cities = Integer.parseInt(in.readLine());
  79. num_of_roads = Integer.parseInt(in.readLine());
  80. for(int i=0; i<num_of_cities ; i++)
  81. {
  82. ArrayList<ArrayList<Pair>> temp = new ArrayList<ArrayList<Pair>>();
  83. ArrayList<Pair> temp2 = new ArrayList<Pair>();
  84. temp2.add(nothing);
  85. for(int j=0;j<num_of_cities ; j++)
  86. {
  87. temp.add(temp2);
  88. }
  89. matrix.add(temp);
  90. }
  91. int road;
  92. int tocity;
  93. int fromcity;
  94. int coast;
  95. StringTokenizer str_tok;
  96. for(int i=0; i<num_of_roads; i++){
  97. str_tok = new StringTokenizer(in.readLine()," ");
  98. fromcity = Integer.parseInt(str_tok.nextToken());
  99. tocity = Integer.parseInt(str_tok.nextToken());
  100. road = Integer.parseInt(str_tok.nextToken());
  101. coast = Integer.parseInt(str_tok.nextToken());
  102. if(matrix.get(fromcity-1).get(tocity-1).get(0).second==-1){
  103. ArrayList<Pair> temp_arr = new ArrayList<Pair>();
  104. temp_arr.add(new Pair(road, coast));
  105. matrix.get(fromcity-1).set(tocity-1,temp_arr);
  106. matrix.get(tocity-1).set(fromcity-1,temp_arr);
  107. }
  108. else{
  109. matrix.get(fromcity-1).get(tocity-1).add(new Pair(road, coast));
  110. //matrix.get(tocity-1).get(fromcity-1).add(new Pair(road, coast));
  111. }
  112. }
  113. str_tok = new StringTokenizer(in.readLine()," ");
  114. start = Integer.parseInt(str_tok.nextToken());
  115. finish = Integer.parseInt(str_tok.nextToken());
  116. PrintWriter fout = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
  117. Four answer = cheepest_way();
  118. if(answer.first==finish){
  119. fout.println("Yes");
  120. fout.printf("%.2f",answer.second);
  121. }
  122. else{
  123. fout.print("No");
  124. }
  125. fout.close();
  126.  
  127. } catch (IOException ex) {
  128. Logger.getLogger(Solution.class.getName()).log(Level.SEVERE, null, ex);
  129. }
  130. }
  131. public static Four cheepest_way(){
  132. PriorityQueue<Four> queue = new PriorityQueue<Four>(1000000, new Four());
  133. Four temp = new Four(start, 0.0, -1,0);
  134. Pair temp2 = new Pair();
  135. for(int i=0;i<num_of_cities;i++){
  136. temp2=(matrix.get(temp.first-1).get(i).get(0));
  137. if(temp2.first!=-1){
  138. for(int j=0;j<matrix.get(temp.first-1).get(i).size();j++){
  139. temp2=(matrix.get(temp.first-1).get(i).get(j));
  140. queue.add(new Four(i+1,(temp.second+(temp2.second+((double)temp2.second/10))),temp.first,j));
  141. }
  142. }
  143. }
  144. while(!queue.isEmpty()){
  145. temp = queue.poll();
  146. if(temp.first==finish)
  147. return temp;
  148.  
  149. for(int i=0;i<num_of_cities;i++){
  150. temp2=(matrix.get(temp.first-1).get(i).get(0));
  151. if(temp2.second!=-1){
  152. for(int j=0;j<matrix.get(temp.first-1).get(i).size();j++){
  153. temp2=(matrix.get(temp.first-1).get(i).get(j));
  154. if(matrix.get(temp.first-1).get(temp.third-1).get(temp.four).first==temp2.first){
  155. queue.add(new Four(i+1,temp.second+temp2.second,temp.first,j));
  156. }
  157. else{
  158. queue.add(new Four(i+1,temp.second+
  159. (temp2.second+(temp2.second/10)),temp.first,j));
  160. }
  161. }
  162. }
  163. }
  164. for(int j=0;j<matrix.get(temp.third-1).get(temp.first-1).size();j++){
  165. int g = matrix.get(temp.third-1).get(temp.first-1).get(j).first;
  166. matrix.get(temp.third-1).get(temp.first-1).set(j,
  167. new Pair(g,-1));
  168. }
  169. }
  170. return temp;
  171. }
  172. }
Add Comment
Please, Sign In to add comment