SHARE
TWEET

Untitled

a guest Feb 23rd, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class F {
  4.  
  5.     /**
  6.      * @param args
  7.      */
  8.     public static void main(String[] args) {
  9.         Scanner scan = new Scanner(System.in);
  10.         int n = scan.nextInt();
  11.         int cases = 1;
  12.         while (n != 0) {
  13.             int[][] adj = new int[n][n];
  14.             for (int i = 0; i < n; i++) {
  15.                 for (int j = 0; j < n; j++) {
  16.                     adj[i][j] = scan.nextInt();
  17.                     if (adj[i][j] == 0) {
  18.                         adj[i][j] = Integer.MAX_VALUE;
  19.                     }
  20.                 }
  21.             }
  22.             int m = scan.nextInt();
  23.             int[] path = new int[m];
  24.             for (int i = 0; i < m; i++) {
  25.                 path[i] = scan.nextInt();
  26.             }
  27.            
  28.             int dist[] = new int[m];
  29.             for (int i = 1; i < m; i++) {
  30.                 dist[i] = dist[i-1] + adj[path[i-1]][path[i]];
  31.             }
  32.            
  33.             //System.out.println(Arrays.toString(dist));
  34.             for (int k = 0; k < n; k++) {
  35.                 for (int i = 0; i < n; i++) {
  36.                     for (int j = 0; j < n; j++) {
  37.                         if (adj[i][k] != Integer.MAX_VALUE && adj[j][k] != Integer.MAX_VALUE)
  38.                             adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
  39.                     }
  40.                 }
  41.             }
  42.             //for (int i = 0; i < n; i++) {
  43.             //  System.out.println(Arrays.toString(adj[i]));
  44.             //}
  45.             int fixed = 0;
  46.             int start = 0;
  47.             for (int i = 1; i < m; i++) {
  48.                 if (adj[path[start]][path[i]] < dist[i]) {
  49.                     for (int j = i+1; j < m; j++) {
  50.                         dist[j] -= (dist[i] - dist[start]);
  51.                     }
  52.                     start = i;
  53.                     fixed++;
  54.                 }      
  55.             }
  56.             System.out.printf("Cases %d: %d", cases, fixed);
  57.             cases++;
  58.             n = scan.nextInt();
  59.             if ( n != 0 )
  60.                 System.out.println();
  61.         }
  62.     }
  63. }
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