結果

問題 No.17 2つの地点に泊まりたい
ユーザー core123core123
提出日時 2019-05-07 13:55:12
言語 Java21
(openjdk 21)
結果
AC  
実行時間 217 ms / 5,000 ms
コード長 1,061 bytes
コンパイル時間 3,064 ms
コンパイル使用メモリ 74,032 KB
実行使用メモリ 59,352 KB
最終ジャッジ日時 2023-09-14 16:26:29
合計ジャッジ時間 8,311 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 127 ms
55,940 KB
testcase_01 AC 125 ms
55,976 KB
testcase_02 AC 132 ms
55,800 KB
testcase_03 AC 157 ms
55,776 KB
testcase_04 AC 185 ms
55,800 KB
testcase_05 AC 214 ms
58,396 KB
testcase_06 AC 194 ms
58,380 KB
testcase_07 AC 191 ms
58,432 KB
testcase_08 AC 217 ms
59,352 KB
testcase_09 AC 216 ms
59,132 KB
testcase_10 AC 197 ms
56,652 KB
testcase_11 AC 201 ms
58,768 KB
testcase_12 AC 127 ms
55,688 KB
testcase_13 AC 125 ms
55,792 KB
testcase_14 AC 125 ms
55,820 KB
testcase_15 AC 126 ms
55,900 KB
testcase_16 AC 125 ms
55,792 KB
testcase_17 AC 135 ms
55,752 KB
testcase_18 AC 155 ms
55,984 KB
testcase_19 AC 148 ms
55,920 KB
testcase_20 AC 134 ms
55,644 KB
testcase_21 AC 130 ms
55,840 KB
testcase_22 AC 158 ms
56,332 KB
testcase_23 AC 204 ms
58,632 KB
testcase_24 AC 202 ms
58,584 KB
testcase_25 AC 140 ms
55,712 KB
testcase_26 AC 212 ms
58,776 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