結果

問題 No.17 2つの地点に泊まりたい
ユーザー ttakanottakano
提出日時 2017-12-04 22:33:59
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,108 bytes
コンパイル時間 2,107 ms
コンパイル使用メモリ 159,488 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-28 04:32:18
合計ジャッジ時間 2,648 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 17
権限があれば一括ダウンロードができます

ソースコード

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

int 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];
  }
  warshall_floyd();
  //REP(i,n)REP(j,n)print(i<<" "<<j<<" "<<d[i][j]);///
  //print(d[0][n-1]);///
  int ans=mod;
  rep(i,1,n-1)rep(j,i+1,n-1){
    int ss=s[i]+s[j];
    int 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