Submission #1691015
Source Code Expand
import java.util.*; public class Main { static Scanner sc = new Scanner(System.in); static int dp[][][]; static int edges[][]; static boolean del[][]; public static void main(String[] args) { int n = sc.nextInt(); edges = new int[n][n]; del = new boolean[n][n]; long total = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { edges[i][j] = sc.nextInt(); total += edges[i][j]; } } dp = new int[n][n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j][0] = edges[i][j]; } } for (int k = 1; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j][k] = Math.min(dp[i][j][k-1], dp[i][k][k-1] + dp[k][j][k-1]); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j && dp[i][j][n-1] != edges[i][j]){ System.out.println(-1); return; } } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i!=j&& j!=k && i !=k &&edges[i][j] == edges[i][k] + edges[k][j] && !del[i][j]) { total -= edges[i][j]; del[i][j] = true; } } } } total /= 2; System.out.println(total); } }
Submission Info
Submission Time | |
---|---|
Task | D - Restoring Road Network |
User | vjudge4 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1656 Byte |
Status | CE |
Compile Error
./Main.cpp:1:1: error: ‘import’ does not name a type import java.util.*; ^ ./Main.cpp:3:1: error: expected unqualified-id before ‘public’ public class Main ^