Ledger Nano X - The secure hardware wallet
SHARE
TWEET

RDNWK - Road Network

a guest Mar 17th, 2018 38 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5. import java.util.Comparator;
  6. import java.util.HashMap;
  7. import java.util.Map;
  8.  
  9. import static java.lang.Integer.min;
  10. import static java.lang.Integer.parseInt;
  11.  
  12. /**
  13.  * Created by bugkiller on 16/03/18.
  14.  */
  15. // problem link http://www.spoj.com/problems/RDNWK/
  16. class RDNWK_RoadNetwork {
  17.  
  18.  
  19.     static int queries[][] = new int[6000][4];//queries[][0],queries[][1],queries[][2] index, k,source, destination
  20.     static int w[][] = new int[151][151];
  21.     static int rankedList[] = new int[151];
  22.     static final int NOT_DEFINED = Integer.MAX_VALUE;
  23.  
  24.     public static void main(String[] args) throws IOException {
  25.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  26.         int t,n,p,q;
  27.         String s[];
  28.         t = parseInt(br.readLine());
  29.         for (int T = 1; T <= t; T++) {
  30.             n = parseInt(br.readLine());
  31.             for (int i = 1; i <= n - 1; i++) {
  32.                 s = br.readLine().split("\\s");
  33.                 int v = i + 1;
  34.                 for (String x : s) {
  35.                     int temp = parseInt(x);
  36.                     if (temp == -1) {
  37.                         temp = NOT_DEFINED;
  38.                     }
  39.                     w[i][v] = temp;
  40.                     w[v][i] = temp;
  41.                     v++;
  42.                 }
  43.             }
  44.             p = parseInt(br.readLine());
  45.             s = br.readLine().split("\\s");
  46.             for (int i = 1; i <= p; i++) {
  47.                 rankedList[i] = parseInt(s[i - 1]);
  48.             }
  49.             q = parseInt(br.readLine());
  50.             for (int i = 0; i < q; i++) {
  51.                 s = br.readLine().split("\\s");
  52.                 queries[i][0] = i;
  53.                 queries[i][1] = parseInt(s[0]);
  54.                 queries[i][2] = parseInt(s[1]);
  55.                 queries[i][3] = parseInt(s[2]);
  56.             }
  57.             Arrays.sort(queries, 0, q, Comparator.comparingInt(query -> query[1]));
  58.             System.out.println("Case "+T+": "+solve(n, p, q));
  59.         }
  60.     }
  61.  
  62.     private static String solve(int n, int p, int q) {
  63.  
  64.         Map<Integer,Integer>map=new HashMap<>();
  65.         StringBuilder sbr = new StringBuilder();
  66.         int query = 0;
  67.         for (int i = 0; i <= p; i++) {
  68.             if (i>0) {
  69.                 for (int j = 1; j <= n; j++) {
  70.                     for (int k = 1; k <= n; k++) {
  71.                         if (w[j][rankedList[i]] != NOT_DEFINED && w[rankedList[i]][k] != NOT_DEFINED) {
  72.                             w[j][k] = min(w[j][k], w[j][rankedList[i]] + w[rankedList[i]][k]);
  73.                         }
  74.                     }
  75.                 }
  76.             }
  77.             while (query < q && queries[query][1] == i) {
  78.                 map.put(queries[query][0], w[queries[query][2]][queries[query][3]]);
  79.                 query++;
  80.             }
  81.         }
  82.         for (int i = 0; i < q; i++) {
  83.             sbr.append(map.get(i)).append(" ");
  84.         }
  85.         sbr.deleteCharAt(sbr.length() - 1);
  86.         return sbr.toString();
  87.     }
  88. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top