VDANGER - Nguy hiểm rõ ràng trước mắt

Tác giả: khuc_tuan

Ngôn ngữ: Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		// Scanner sc = new Scanner(System.in);
		StringTokenizer st = new StringTokenizer(kb.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[] ds = new int[m];
		for (int i = 0; i < m; ++i)
			ds[i] = Integer.parseInt(kb.readLine()) - 1;
		int[][] a = new int[n][n];
		for (int i = 0; i < n; ++i) {
			st = new StringTokenizer(kb.readLine());
			for (int j = 0; j < n; ++j)
				a[i][j] = Integer.parseInt(st.nextToken());
		}
		for (int k = 0; k < n; ++k)
			for (int i = 0; i < n; ++i)
				for (int j = 0; j < n; ++j)
					a[i][j] = Math.min(a[i][j], a[i][k] + a[k][j]);
		int s = 0;
		long total = 0;
		for (int i = 0; i < ds.length; ++i) {
			total += a[s][ds[i]];
			s = ds[i];
		}
		total += a[s][n - 1];
		System.out.println(total);
	}
}

Download