結果

問題 No.17 2つの地点に泊まりたい
ユーザー core123core123
提出日時 2019-05-07 13:55:12
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 132 ms
41,020 KB
testcase_01 AC 131 ms
40,924 KB
testcase_02 AC 138 ms
41,192 KB
testcase_03 AC 160 ms
41,452 KB
testcase_04 AC 172 ms
41,844 KB
testcase_05 AC 217 ms
44,296 KB
testcase_06 AC 202 ms
42,820 KB
testcase_07 AC 197 ms
42,720 KB
testcase_08 AC 222 ms
45,264 KB
testcase_09 AC 224 ms
45,152 KB
testcase_10 AC 202 ms
42,048 KB
testcase_11 AC 206 ms
42,996 KB
testcase_12 AC 121 ms
39,920 KB
testcase_13 AC 130 ms
41,572 KB
testcase_14 AC 132 ms
41,128 KB
testcase_15 AC 133 ms
41,164 KB
testcase_16 AC 135 ms
41,076 KB
testcase_17 AC 141 ms
41,012 KB
testcase_18 AC 153 ms
41,388 KB
testcase_19 AC 153 ms
41,440 KB
testcase_20 AC 141 ms
41,168 KB
testcase_21 AC 137 ms
41,160 KB
testcase_22 AC 161 ms
41,824 KB
testcase_23 AC 207 ms
43,852 KB
testcase_24 AC 206 ms
42,976 KB
testcase_25 AC 147 ms
41,524 KB
testcase_26 AC 213 ms
44,720 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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