結果

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

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define printall(n,array) for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;
typedef long long ll;
typedef pair<int, int> PI;
typedef pair<int, PI> V;
typedef vector<int> VE;
const ll mod = 1000000007; //10^9+7

ll d[52][52];
int n;
int m;
int s[52];
int a[1300];
int b[1300];
int c[1300];

void warshall_floyd(){
  REP(k,n){
    REP(i,n){
      REP(j,n){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        d[j][i]=d[i][j];
      }
    }
  }
}

int main(){
  cin>>n;
  REP(i,n)cin>>s[i];
  cin>>m;
  REP(i,n)REP(j,n)d[i][j]=mod;
  REP(i,n)d[i][i]=0;
  REP(i,m){
    cin>>a[i]>>b[i]>>c[i];
    d[a[i]][b[i]]=c[i];
    d[b[i]][a[i]]=c[i];
  }
  warshall_floyd();
  //REP(i,n)REP(j,n)print(i<<" "<<j<<" "<<d[i][j]);///
  //print(d[0][n-1]);///
  ll ans=mod;
  rep(i,1,n-1)rep(j,i+1,n-1){
    int ss=s[i]+s[j];
    ll min_=min(d[0][i]+d[i][j]+d[j][n-1],d[0][j]+d[i][j]+d[i][n-1]);
    ///print(i<<" "<<j<<" "<<min_<<" "<<ss);
    ans=min(ans,min_+ss);
  }
  print(ans);
}
0