結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー Han Lin
提出日時 2023-02-24 03:48:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 795 bytes
コンパイル時間 1,688 ms
コンパイル使用メモリ 167,948 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-23 19:36:12
合計ジャッジ時間 2,737 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

const int N = 50 + 10;
const int inf = 1000000000;

int g[N][N];
int s[N];

int main() {
	int n, m, u, v, w;
	cin >> n;
	for (int i=1; i<=n; i++) cin >> s[i];
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			if (i == j) g[i][j] = 0; else g[i][j] = inf;
		}
	}
	cin >> m;
	for (int i=0; i<m; i++) {
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = min(g[u][v], w);
	}
	for (int k=1; k<=n; k++) {
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
		}
	}
	int res = inf;
	for (int i=2; i<n-1; i++) {
		for (int j=i+1; j<n; j++) {
			res = min(res, g[1][i] + s[i] + g[i][j] + s[j] + g[j][n]);
			res = min(res, g[1][j] + s[j] + g[j][i]+ s[i] + g[i][n]);
		}
	}
	cout << res << endl;
	return 0;
}
0