fork download
copy 
  1. import java.util.*;
  2.  
  3. class C_RoadsInBerland {
  4. 	public static void main(String[] args) throws Exception {
  5. 		Scanner scan = new Scanner(System.in);
  6. 		int n = scan.nextInt(); // 2-300
  7. 		int[][] a = new int[n][n];
  8. 		for (int i = 0; i < n; i++) {
  9. 			for (int j = 0; j < n; j++) {
  10. 				a[i][j] = scan.nextInt();
  11. 			}
  12. 		}
  13. 		StringBuffer result = new StringBuffer();
  14. 		for (int k = scan.nextInt(); k-- > 0;) { // 1-300
  15. 			int x = scan.nextInt() - 1, y = scan.nextInt() - 1, z = scan
  16. 					.nextInt();
  17. 			a[x][y] = a[y][x] = Math.min(a[x][y],z);
  18. 			for(int t:new int[]{x,y}){
  19. 				for (int i = 0; i < n-1; i++) {
  20. 					for (int j = i+1; j < n; j++) {
  21. 						if(a[i][j] > a[i][t]+a[t][j]){
  22. 							a[i][j] = a[j][i] = a[i][t]+a[t][j];
  23. 						}
  24. 					}
  25. 				}
  26. 			}
  27. 			long sum = 0;
  28. 			for (int i = 0; i < n-1; i++) {
  29. 				for (int j = i+1; j < n; j++) {
  30. 					sum += a[i][j];
  31. 				}
  32. 			}
  33. 			result.append(sum);
  34. 			result.append(" ");
  35. 		}
  36. 		System.out.println(result.replace(result.length()-1, result.length(), ""));
  37. 	}
  38.  
  39. }
  40.  
Success #stdin #stdout 0.07s 213760KB
comments (?)
stdin
copy 
2
0 5
5 0
1
1 2 3
stdout
copy 
3
https://ideone.com/lppub
language:
Java (HotSpot 12)
created:
15 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!