結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー リチウム
提出日時 2014-11-17 22:56:14
言語 Java
(openjdk 23)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,065 bytes
コンパイル時間 2,438 ms
コンパイル使用メモリ 80,556 KB
実行使用メモリ 56,616 KB
最終ジャッジ日時 2025-01-02 16:48:52
合計ジャッジ時間 7,326 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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