Codeforces #25 C "Roads in Berland"

問題:http://codeforces.com/contest/25/problem/C

ワーシャルフロイド的なものでやってみた.
テストケース38で最短経路合計値のint->longにするまでハマってた.
いろいろ無駄がありそう.

import java.util.Scanner;

public class C {
	public static void main(String[] args) throws Exception {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(); // 2-300
		int[][] a = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				a[i][j] = scan.nextInt();
			}
		}
		StringBuffer result = new StringBuffer();
		for (int k = scan.nextInt(); k-- > 0;) { // 1-300
			int x = scan.nextInt() - 1, y = scan.nextInt() - 1, z = scan
					.nextInt();
			a[x][y] = a[y][x] = Math.min(a[x][y],z);
			for(int t:new int[]{x,y}){
				for (int i = 0; i < n-1; i++) {
					for (int j = i+1; j < n; j++) {
						if(a[i][j]>a[i][t]+a[t][j]){
							a[i][j]=a[j][i]=a[i][t]+a[t][j];
						}
					}
				}
			}
			long sum = 0;
			for (int i = 0; i < n-1; i++) {
				for (int j = i+1; j < n; j++) {
					sum += a[i][j];
				}
			}
			result.append(sum);
			result.append(" ");
		}
		System.out.println(result.replace(result.length()-1,result.length(),""));
	}

}