Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Copy paste this Java Template and save it as "OutForAWalk.java"
- import java.util.*;
- import java.io.*;
- // write your matric number here: A0124487Y
- // write your name here: Low Yang Tse
- // write list of collaborators here:
- // year 2015 hash code: JESg5svjYpIsmHmIjabX (do NOT delete this line)
- class OutForAWalk {
- private int V; // number of vertices in the graph (number of rooms in the building)
- private Vector < Vector < IntegerPair > > AdjList; // the weighted graph (the building), effort rating of each corridor is stored here too
- private Vector < Vector < IntegerPair > > MST = new Vector < Vector < IntegerPair > >();
- public boolean[] visited = new boolean [V];
- public int arr[][] = new int[10][2000];
- // if needed, declare a private data structure here that
- // is accessible to all methods in this class
- // --------------------------------------------
- // --------------------------------------------
- public OutForAWalk() {
- // Write necessary codes during construction;
- //
- // write your answer here
- }
- void PreProcess() { //(correct)
- MST = new Vector < Vector < IntegerPair > >();
- int countVisited = 1;
- visited = new boolean [V];
- for (int i = 0; i < V; i++) { //this adds vector<integerpair> into the vectors
- MST.add(new Vector < IntegerPair >());
- }
- PriorityQueue <IntegerTriple> pq = new PriorityQueue <IntegerTriple>(V);
- int nodeA = 0; //this refers to the current node being analyzed
- visited[nodeA] = true;
- for(int i = 0; i < AdjList.get(nodeA).size(); i++) { //this adds 0th neighbor into queue
- int b = AdjList.get(nodeA).get(i).first();
- int weight = AdjList.get(nodeA).get(i).second();
- pq.add(new IntegerTriple(weight, nodeA , b)); //(weight, A, B)
- }
- while(pq.peek() != null && countVisited!=V) {
- IntegerTriple edge = pq.poll();
- nodeA = edge.second(); //makes nodeA the first pq that it is from
- int nodeB = edge.third();
- int weight = edge.first();
- if(!visited[nodeB]) {
- countVisited++;
- visited[nodeB] = true;
- MST.get(nodeA).add(new IntegerPair(nodeB, weight));
- MST.get(nodeB).add(new IntegerPair(nodeA, weight));
- for(int i = 0; i < AdjList.get(nodeB).size(); i++) { //this adds nodeB neighbor into queue
- int b = AdjList.get(nodeB).get(i).first();
- weight = AdjList.get(nodeB).get(i).second();
- pq.offer(new IntegerTriple(weight, nodeB , b)); //(weight, A, B)
- }
- }
- }
- //start storing
- arr = new int[10][2000];
- int x;
- if(V < 10) {
- x= V;
- } else {
- x = 10;
- }
- for (int i = 0; i < x; i++) {
- visited = new boolean[V];
- dfs(MST, i, 0, i);
- // System.out.println(" ");
- // printArr(arr, i);
- }
- }
- void printArr (int[][] arr, int i) {
- for (int j = 0; j < V; j++) {
- System.out.print("(" + arr[i][j] + ")");
- }
- System.out.println(" ");
- }
- int Query(int source, int destination) {
- return arr[source][destination];
- }
- /*
- void printMST(Vector<Vector<IntegerPair>> MST) {
- for(int i = 0; i < V; i++) {
- System.out.print(i + "th node: ");
- for (int j = 0; j<MST.get(i).size(); j++) {
- int first = MST.get(i).get(j).first();
- int second = MST.get(i).get(j).second();
- System.out.print(" ("+first+ " " + second + ")");
- }
- System.out.println(" ");
- }
- System.out.println(" ");
- }
- */
- // You can add extra function if needed
- // --------------------------------------------
- void dfs(Vector<Vector<IntegerPair>> MST, int source, int maximum, int initial) {
- // System.out.println("Currently at vertice : " + source);
- if(source == initial) {
- arr[initial][initial] = 0;
- }
- visited[source] = true;
- for(int i = 0; i < MST.get(source).size(); i++) { //search for all neighbours
- IntegerPair edge = MST.get(source).get(i);
- if(!visited[edge.first()]) {
- // System.out.println("Currently at vertice : " + edge.first());
- // System.out.println("Current maximum: " + maximum);
- if(edge.second() > maximum) {
- arr[initial][edge.first()] = edge.second();
- dfs(MST, edge.first(), edge.second(), initial);
- } else {
- arr[initial][edge.first()] = maximum;
- dfs(MST, edge.first(), maximum, initial);
- }
- }
- }
- // System.out.println(" ");
- }
- // --------------------------------------------
- void run() throws Exception {
- // do not alter this method
- IntegerScanner sc = new IntegerScanner(System.in);
- PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
- int TC = sc.nextInt(); // there will be several test cases
- while (TC-- > 0) {
- V = sc.nextInt();
- // clear the graph and read in a new graph as Adjacency List
- AdjList = new Vector < Vector < IntegerPair > >();
- for (int i = 0; i < V; i++) {
- AdjList.add(new Vector < IntegerPair >());
- int k = sc.nextInt();
- while (k-- > 0) {
- int j = sc.nextInt(), w = sc.nextInt();
- AdjList.get(i).add(new IntegerPair(j, w)); // edge (corridor) weight (effort rating) is stored here
- }
- }
- PreProcess(); // you may want to use this function or leave it empty if you do not need it
- int Q = sc.nextInt();
- while (Q-- > 0)
- pr.println(Query(sc.nextInt(), sc.nextInt()));
- pr.println(); // separate the answer between two different graphs
- }
- pr.close();
- }
- public static void main(String[] args) throws Exception {
- // do not alter this method
- OutForAWalk ps4 = new OutForAWalk();
- ps4.run();
- }
- }
- class IntegerScanner { // coded by Ian Leow, using any other I/O method is not recommended
- BufferedInputStream bis;
- IntegerScanner(InputStream is) {
- bis = new BufferedInputStream(is, 1000000);
- }
- public int nextInt() {
- int result = 0;
- try {
- int cur = bis.read();
- if (cur == -1)
- return -1;
- while ((cur < 48 || cur > 57) && cur != 45) {
- cur = bis.read();
- }
- boolean negate = false;
- if (cur == 45) {
- negate = true;
- cur = bis.read();
- }
- while (cur >= 48 && cur <= 57) {
- result = result * 10 + (cur - 48);
- cur = bis.read();
- }
- if (negate) {
- return -result;
- }
- return result;
- }
- catch (IOException ioe) {
- return -1;
- }
- }
- }
- class IntegerPair implements Comparable < IntegerPair > {
- Integer _first, _second;
- public IntegerPair(Integer f, Integer s) {
- _first = f;
- _second = s;
- }
- public int compareTo(IntegerPair o) {
- if (!this.first().equals(o.first()))
- return this.first() - o.first();
- else
- return this.second() - o.second();
- }
- Integer first() { return _first; }
- Integer second() { return _second; }
- }
- //
- class IntegerTriple implements Comparable < IntegerTriple > {
- Integer _first, _second, _third;
- public IntegerTriple(Integer f, Integer s, Integer t) {
- _first = f;
- _second = s;
- _third = t;
- }
- public int compareTo(IntegerTriple o) {
- if (!this.first().equals(o.first()))
- return this.first() - o.first();
- else if (!this.second().equals(o.second()))
- return this.second() - o.second();
- else
- return this.third() - o.third();
- }
- Integer first() { return _first; }
- Integer second() { return _second; }
- Integer third() { return _third; }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement