#2600 (C++11) No.17 2つの地点に泊まりたい

• 問題: No.17 2つの地点に泊まりたい
• ユーザー: ciel
• 提出日時: 2014-11-16 18:06:31
• 言語: C++11 (gcc 11.4.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 757 bytes
• コンパイル時間: 489 ms
• コンパイル使用メモリ: 41,720 KB
• 実行使用メモリ: 4,384 KB
• 最終ジャッジ日時: 2023-08-30 07:15:01
• 合計ジャッジ時間: 1,918 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,376 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	2 ms; 4,376 KB
testcase_06	AC	1 ms; 4,376 KB
testcase_07	AC	2 ms; 4,380 KB
testcase_08	AC	2 ms; 4,376 KB
testcase_09	AC	2 ms; 4,376 KB
testcase_10	AC	2 ms; 4,380 KB
testcase_11	AC	3 ms; 4,380 KB
testcase_12	AC	1 ms; 4,376 KB
testcase_13	AC	2 ms; 4,376 KB
testcase_14	AC	1 ms; 4,376 KB
testcase_15	AC	2 ms; 4,376 KB
testcase_16	AC	2 ms; 4,376 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	AC	2 ms; 4,376 KB
testcase_24	AC	2 ms; 4,376 KB
testcase_25	AC	1 ms; 4,376 KB
testcase_26	AC	2 ms; 4,380 KB

ソースコード

#include <vector>
#include <cstdio>
using namespace std;

int main(){
	int n,m;
	scanf("%d",&n);
	vector<int>cost(n);
	vector<vector<int> >dist(n);
	for(int i=0;i<n;i++){
		scanf("%d",&cost[i]);
		dist[i].resize(n);
		for(int j=0;j<n;j++)dist[i][j]=999999999;
		dist[i][i]=0;
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		dist[a][b]=dist[b][a]=c;
	}
	for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)
		if(dist[i][j]>dist[i][k]+dist[k][j])dist[i][j]=dist[i][k]+dist[k][j];
	int ma=999999999;
	for(int i=1;i<n-1;i++)for(int j=1;j<n-1;j++)
		if(i!=j&&ma>dist[0][i]+cost[i]+dist[i][j]+cost[j]+dist[j][n-1])ma=dist[0][i]+cost[i]+dist[i][j]+cost[j]+dist[j][n-1];
	printf("%d\n",ma);
}