結果

問題 No.17 2つの地点に泊まりたい
ユーザー リチウムリチウム
提出日時 2014-11-17 22:56:14
言語 Java21
(openjdk 21)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,065 bytes
コンパイル時間 2,016 ms
コンパイル使用メモリ 77,960 KB
実行使用メモリ 45,568 KB
最終ジャッジ日時 2024-06-10 19:58:07
合計ジャッジ時間 6,978 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 114 ms
41,068 KB
testcase_01 AC 99 ms
40,060 KB
testcase_02 AC 120 ms
41,168 KB
testcase_03 AC 145 ms
41,740 KB
testcase_04 AC 159 ms
42,376 KB
testcase_05 AC 183 ms
44,356 KB
testcase_06 AC 170 ms
43,448 KB
testcase_07 AC 170 ms
42,984 KB
testcase_08 AC 195 ms
45,340 KB
testcase_09 AC 199 ms
45,568 KB
testcase_10 AC 172 ms
42,784 KB
testcase_11 AC 179 ms
43,616 KB
testcase_12 AC 109 ms
41,108 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 184 ms
44,000 KB
testcase_24 AC 180 ms
43,512 KB
testcase_25 AC 123 ms
41,292 KB
testcase_26 AC 173 ms
44,532 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import java.util.*;

public class Main {
	
	static Scanner sc;
	static int n,m;
	static void Warshall_Floyd_Algorithm(int n, int N[][]) {
		for (int i = 0; i < n; i++) {
			Arrays.fill(N[i], Integer.MAX_VALUE / 2);
			N[i][i] = 0;
		}
		for(int i=0;i<m;i++){
			int x=sc.nextInt();
			int y=sc.nextInt();
			int c=sc.nextInt();
			N[x][y]=N[y][x]=c;
		}
		//初期条件をここに挿入
		for (int k = 0; k < n; ++k) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < n; ++j) {
					N[i][j] = Math.min(N[i][j], N[i][k] + N[k][j]);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		sc=new Scanner(System.in);
		n=sc.nextInt();
		int s[]=new int[n];
		for(int i=0;i<n;i++){
			s[i]=sc.nextInt();
		}
		int map[][]=new int[n][n];
		
		m=sc.nextInt();
		Warshall_Floyd_Algorithm(n,map);
		int ans=Integer.MAX_VALUE;
		for(int i=1;i<n-1;i++){
			for(int j=1;j<n-1;j++){
				if(i==j)continue;
				ans=Math.min(ans,map[0][i]+s[i]+map[i][j]+s[j]+map[j][n-1]);
			}
		}
		System.out.println(ans);
		
	}}
0