結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー core123
提出日時 2019-05-07 13:55:12
言語 Java
(openjdk 23)
結果
AC  
実行時間 224 ms / 5,000 ms
コード長 1,061 bytes
コンパイル時間 2,112 ms
コンパイル使用メモリ 77,424 KB
実行使用メモリ 45,264 KB
最終ジャッジ日時 2024-07-01 23:33:52
合計ジャッジ時間 7,659 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import static java.lang.Math.*;

import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] s=new int[n];
		for(int i=0;i<n;i++) {
			s[i]=sc.nextInt();
		}
		int m=sc.nextInt();
		int[][] graph=new int[n][n];
		for(int i=0;i<n;i++) {
			Arrays.fill(graph[i], Integer.MAX_VALUE>>4);
		}
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int c=sc.nextInt();
			graph[a][b]=c;
			graph[b][a]=c;
		}
		for(int i=0;i<n;i++) {
			//System.out.println(Arrays.toString(graph[i]));
		}
		int[][] d=new int[n][n];
		for(int i=0;i<n;i++) {
			d[i]=graph[i];
		}
		for(int k=0;k<n;k++) {
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
				}
			}
		}
		int min=Integer.MAX_VALUE;
		for(int i=1;i<n-1;i++) {
			for(int j=1;j<n-1;j++) {
				if(i==j)continue;
				min=min(min,d[0][i]+s[i]+d[i][j]+s[j]+d[j][n-1]);
			}
		}
		System.out.println(min);
	}

}
0