Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.Arrays;
- import java.util.Comparator;
- import java.util.HashMap;
- import java.util.Map;
- import static java.lang.Integer.min;
- import static java.lang.Integer.parseInt;
- /**
- * Created by bugkiller on 16/03/18.
- */
- // problem link http://www.spoj.com/problems/RDNWK/
- class RDNWK_RoadNetwork {
- static int queries[][] = new int[6000][4];//queries[][0],queries[][1],queries[][2] index, k,source, destination
- static int w[][] = new int[151][151];
- static int rankedList[] = new int[151];
- static final int NOT_DEFINED = Integer.MAX_VALUE;
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- int t,n,p,q;
- String s[];
- t = parseInt(br.readLine());
- for (int T = 1; T <= t; T++) {
- n = parseInt(br.readLine());
- for (int i = 1; i <= n - 1; i++) {
- s = br.readLine().split("\\s");
- int v = i + 1;
- for (String x : s) {
- int temp = parseInt(x);
- if (temp == -1) {
- temp = NOT_DEFINED;
- }
- w[i][v] = temp;
- w[v][i] = temp;
- v++;
- }
- }
- p = parseInt(br.readLine());
- s = br.readLine().split("\\s");
- for (int i = 1; i <= p; i++) {
- rankedList[i] = parseInt(s[i - 1]);
- }
- q = parseInt(br.readLine());
- for (int i = 0; i < q; i++) {
- s = br.readLine().split("\\s");
- queries[i][0] = i;
- queries[i][1] = parseInt(s[0]);
- queries[i][2] = parseInt(s[1]);
- queries[i][3] = parseInt(s[2]);
- }
- Arrays.sort(queries, 0, q, Comparator.comparingInt(query -> query[1]));
- System.out.println("Case "+T+": "+solve(n, p, q));
- }
- }
- private static String solve(int n, int p, int q) {
- Map<Integer,Integer>map=new HashMap<>();
- StringBuilder sbr = new StringBuilder();
- int query = 0;
- for (int i = 0; i <= p; i++) {
- if (i>0) {
- for (int j = 1; j <= n; j++) {
- for (int k = 1; k <= n; k++) {
- if (w[j][rankedList[i]] != NOT_DEFINED && w[rankedList[i]][k] != NOT_DEFINED) {
- w[j][k] = min(w[j][k], w[j][rankedList[i]] + w[rankedList[i]][k]);
- }
- }
- }
- }
- while (query < q && queries[query][1] == i) {
- map.put(queries[query][0], w[queries[query][2]][queries[query][3]]);
- query++;
- }
- }
- for (int i = 0; i < q; i++) {
- sbr.append(map.get(i)).append(" ");
- }
- sbr.deleteCharAt(sbr.length() - 1);
- return sbr.toString();
- }
- }
Add Comment
Please, Sign In to add comment