daily pastebin goal
55%
SHARE
TWEET

Untitled

a guest Apr 16th, 2018 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Solution {
  5.     public static void main(String[] args) {
  6.         Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
  7.         int t = in.nextInt();
  8.         for (int i = 1; i <= t; ++i) {
  9.             int n = in.nextInt();
  10.             int m = in.nextInt();
  11.             int p = in.nextInt();
  12.             int[][] d = new int[n][n];
  13.             for (int j = 0; j < n; ++j) {
  14.                 for (int k = 0; k < n; ++k) {
  15.                     d[j][k] = Integer.MAX_VALUE / n;
  16.                 }
  17.             }
  18.             for (int j = 0; j < m; ++j) {
  19.                 int u = in.nextInt();
  20.                 int v = in.nextInt();
  21.                 int di = in.nextInt();
  22.                 d[u - 1][v - 1] = di;
  23.                 d[v - 1][u - 1] = di;
  24.             }
  25.             for (int j = 0; j < n; ++j) {
  26.                 for (int k = 0; k < n; ++k) {
  27.                     for (int l = 0; l < n; ++l) {
  28.                         d[k][l] = Math.min(d[k][l], d[k][j] + d[j][l]);
  29.                     }
  30.                 }
  31.             }
  32.             double[][] dp = new double[p + 1][n];
  33.             for (int j = 1; j <= p; ++j) {
  34.                 for (int k = 0; k < n; ++k) {
  35.                     for (int l = 0; l < n; ++l) {
  36.                         if (k != l) {
  37.                             dp[j][k] += (dp[j - 1][l] + d[l][k]) / (n - 1);
  38.                         }
  39.                     }
  40.                 }
  41.             }
  42.             System.out.println("Case #" + i + ": " + dp[p][0]);
  43.         }
  44.         in.close();
  45.     }
  46. }
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