結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー newlife171128
提出日時 2018-02-07 21:53:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,301 bytes
コンパイル時間 1,277 ms
コンパイル使用メモリ 158,660 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 01:42:47
合計ジャッジ時間 1,906 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include "bits/stdc++.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <stdio.h>
#include <map>
#include <unordered_map>
#include <string.h>
#include <utility>

typedef long long ll;
const int INF = 1e8;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;

typedef pair<int, int> P;

int city[51][51];
int stay_cost[51];


int main() {

	int n=0;
	cin>>n;



	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i !=j){
			city[i][j] =INF;
			}
		}

	}

	int tmp=0;
	for(int i=0; i<n; i++){
		cin>>tmp;
		stay_cost[i] =tmp;

	}

	int m=0;
	cin>>m;

	int s ,t, c;
	for(int i=0; i<m; i++){
		cin>>s>>t>>c;

		city[s][t] =c;
		city[t][s] =c;
	}
/*
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout<<city[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;*/

	for(int k=0; k<n; k++){
		for(int i=0; i<n;i++){
			for(int j=0; j<n; j++){

				city[i][j] = min(city[i][j],city[i][k]+city[k][j]);
			}
		}
	}
	int ans =1e8;

	for(int k=1; k<n-1; k++){
		for(int i=1; i<n-1;i++){

			if( k !=i)
				ans = min(ans, city[0][k]+city[k][i]+city[i][n-1]+stay_cost[k]+stay_cost[i]);

		}
	}

	cout<<ans<<endl;
	return 0;
}
0