Advertisement
skippeed

Untitled

Oct 10th, 2015
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.63 KB | None | 0 0
  1. // Copy paste this Java Template and save it as "OutForAWalk.java"
  2. import java.util.*;
  3. import java.io.*;
  4.  
  5. // write your matric number here: A0124487Y
  6. // write your name here: Low Yang Tse
  7. // write list of collaborators here:
  8. // year 2015 hash code: JESg5svjYpIsmHmIjabX (do NOT delete this line)
  9.  
  10. class OutForAWalk {
  11. private int V; // number of vertices in the graph (number of rooms in the building)
  12. private Vector < Vector < IntegerPair > > AdjList; // the weighted graph (the building), effort rating of each corridor is stored here too
  13. private Vector < Vector < IntegerPair > > MST = new Vector < Vector < IntegerPair > >();
  14. public boolean[] visited = new boolean [V];
  15. public int arr[][] = new int[10][2000];
  16. // if needed, declare a private data structure here that
  17. // is accessible to all methods in this class
  18. // --------------------------------------------
  19.  
  20.  
  21.  
  22. // --------------------------------------------
  23.  
  24. public OutForAWalk() {
  25. // Write necessary codes during construction;
  26. //
  27. // write your answer here
  28. }
  29.  
  30. void PreProcess() { //(correct)
  31. MST = new Vector < Vector < IntegerPair > >();
  32. int countVisited = 1;
  33. visited = new boolean [V];
  34.  
  35. for (int i = 0; i < V; i++) { //this adds vector<integerpair> into the vectors
  36. MST.add(new Vector < IntegerPair >());
  37. }
  38. PriorityQueue <IntegerTriple> pq = new PriorityQueue <IntegerTriple>(V);
  39. int nodeA = 0; //this refers to the current node being analyzed
  40. visited[nodeA] = true;
  41.  
  42. for(int i = 0; i < AdjList.get(nodeA).size(); i++) { //this adds 0th neighbor into queue
  43. int b = AdjList.get(nodeA).get(i).first();
  44. int weight = AdjList.get(nodeA).get(i).second();
  45. pq.add(new IntegerTriple(weight, nodeA , b)); //(weight, A, B)
  46. }
  47. while(pq.peek() != null && countVisited!=V) {
  48. IntegerTriple edge = pq.poll();
  49. nodeA = edge.second(); //makes nodeA the first pq that it is from
  50. int nodeB = edge.third();
  51. int weight = edge.first();
  52. if(!visited[nodeB]) {
  53. countVisited++;
  54. visited[nodeB] = true;
  55. MST.get(nodeA).add(new IntegerPair(nodeB, weight));
  56. MST.get(nodeB).add(new IntegerPair(nodeA, weight));
  57.  
  58. for(int i = 0; i < AdjList.get(nodeB).size(); i++) { //this adds nodeB neighbor into queue
  59. int b = AdjList.get(nodeB).get(i).first();
  60. weight = AdjList.get(nodeB).get(i).second();
  61. pq.offer(new IntegerTriple(weight, nodeB , b)); //(weight, A, B)
  62. }
  63. }
  64. }
  65.  
  66. //start storing
  67. arr = new int[10][2000];
  68. int x;
  69. if(V < 10) {
  70. x= V;
  71. } else {
  72. x = 10;
  73. }
  74. for (int i = 0; i < x; i++) {
  75. visited = new boolean[V];
  76. dfs(MST, i, 0, i);
  77. // System.out.println(" ");
  78. // printArr(arr, i);
  79. }
  80.  
  81. }
  82.  
  83. void printArr (int[][] arr, int i) {
  84. for (int j = 0; j < V; j++) {
  85. System.out.print("(" + arr[i][j] + ")");
  86. }
  87. System.out.println(" ");
  88. }
  89.  
  90. int Query(int source, int destination) {
  91. return arr[source][destination];
  92. }
  93. /*
  94. void printMST(Vector<Vector<IntegerPair>> MST) {
  95. for(int i = 0; i < V; i++) {
  96. System.out.print(i + "th node: ");
  97. for (int j = 0; j<MST.get(i).size(); j++) {
  98. int first = MST.get(i).get(j).first();
  99. int second = MST.get(i).get(j).second();
  100. System.out.print(" ("+first+ " " + second + ")");
  101. }
  102. System.out.println(" ");
  103. }
  104. System.out.println(" ");
  105. }
  106. */
  107. // You can add extra function if needed
  108. // --------------------------------------------
  109. void dfs(Vector<Vector<IntegerPair>> MST, int source, int maximum, int initial) {
  110. // System.out.println("Currently at vertice : " + source);
  111. if(source == initial) {
  112. arr[initial][initial] = 0;
  113. }
  114. visited[source] = true;
  115. for(int i = 0; i < MST.get(source).size(); i++) { //search for all neighbours
  116. IntegerPair edge = MST.get(source).get(i);
  117. if(!visited[edge.first()]) {
  118. // System.out.println("Currently at vertice : " + edge.first());
  119. // System.out.println("Current maximum: " + maximum);
  120. if(edge.second() > maximum) {
  121. arr[initial][edge.first()] = edge.second();
  122. dfs(MST, edge.first(), edge.second(), initial);
  123. } else {
  124. arr[initial][edge.first()] = maximum;
  125. dfs(MST, edge.first(), maximum, initial);
  126. }
  127. }
  128. }
  129. // System.out.println(" ");
  130. }
  131.  
  132.  
  133. // --------------------------------------------
  134.  
  135. void run() throws Exception {
  136. // do not alter this method
  137. IntegerScanner sc = new IntegerScanner(System.in);
  138. PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  139.  
  140. int TC = sc.nextInt(); // there will be several test cases
  141. while (TC-- > 0) {
  142. V = sc.nextInt();
  143.  
  144. // clear the graph and read in a new graph as Adjacency List
  145. AdjList = new Vector < Vector < IntegerPair > >();
  146. for (int i = 0; i < V; i++) {
  147. AdjList.add(new Vector < IntegerPair >());
  148.  
  149. int k = sc.nextInt();
  150. while (k-- > 0) {
  151. int j = sc.nextInt(), w = sc.nextInt();
  152. AdjList.get(i).add(new IntegerPair(j, w)); // edge (corridor) weight (effort rating) is stored here
  153. }
  154. }
  155.  
  156. PreProcess(); // you may want to use this function or leave it empty if you do not need it
  157.  
  158. int Q = sc.nextInt();
  159. while (Q-- > 0)
  160. pr.println(Query(sc.nextInt(), sc.nextInt()));
  161. pr.println(); // separate the answer between two different graphs
  162. }
  163.  
  164. pr.close();
  165. }
  166.  
  167. public static void main(String[] args) throws Exception {
  168. // do not alter this method
  169. OutForAWalk ps4 = new OutForAWalk();
  170. ps4.run();
  171. }
  172. }
  173.  
  174.  
  175. class IntegerScanner { // coded by Ian Leow, using any other I/O method is not recommended
  176. BufferedInputStream bis;
  177. IntegerScanner(InputStream is) {
  178. bis = new BufferedInputStream(is, 1000000);
  179. }
  180.  
  181. public int nextInt() {
  182. int result = 0;
  183. try {
  184. int cur = bis.read();
  185. if (cur == -1)
  186. return -1;
  187.  
  188. while ((cur < 48 || cur > 57) && cur != 45) {
  189. cur = bis.read();
  190. }
  191.  
  192. boolean negate = false;
  193. if (cur == 45) {
  194. negate = true;
  195. cur = bis.read();
  196. }
  197.  
  198. while (cur >= 48 && cur <= 57) {
  199. result = result * 10 + (cur - 48);
  200. cur = bis.read();
  201. }
  202.  
  203. if (negate) {
  204. return -result;
  205. }
  206. return result;
  207. }
  208. catch (IOException ioe) {
  209. return -1;
  210. }
  211. }
  212. }
  213.  
  214.  
  215.  
  216. class IntegerPair implements Comparable < IntegerPair > {
  217. Integer _first, _second;
  218.  
  219. public IntegerPair(Integer f, Integer s) {
  220. _first = f;
  221. _second = s;
  222. }
  223.  
  224. public int compareTo(IntegerPair o) {
  225. if (!this.first().equals(o.first()))
  226. return this.first() - o.first();
  227. else
  228. return this.second() - o.second();
  229. }
  230.  
  231. Integer first() { return _first; }
  232. Integer second() { return _second; }
  233. }
  234.  
  235.  
  236. //
  237. class IntegerTriple implements Comparable < IntegerTriple > {
  238. Integer _first, _second, _third;
  239.  
  240. public IntegerTriple(Integer f, Integer s, Integer t) {
  241. _first = f;
  242. _second = s;
  243. _third = t;
  244. }
  245.  
  246. public int compareTo(IntegerTriple o) {
  247. if (!this.first().equals(o.first()))
  248. return this.first() - o.first();
  249. else if (!this.second().equals(o.second()))
  250. return this.second() - o.second();
  251. else
  252. return this.third() - o.third();
  253. }
  254.  
  255. Integer first() { return _first; }
  256. Integer second() { return _second; }
  257. Integer third() { return _third; }
  258. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement