yukicoder no.17 - Logfiles

問題文
http://ch.nicovideo.jp/programing/blomaga/ar607615

解法
WF + 全探索（中継点決め打ち）

類題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2200

#include <iostream>
#include <algorithm>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

#define INF (1<<29)

int main() {
  
  int N; cin >> N;
  int S[N];
  rep(i,N) cin >> S[i];
  
  int C[N][N];
  fill(C[0], C[0]+N*N, INF);
  rep(i,N) C[i][i] = 0;
  
  int M; cin >> M;
  rep(i,M) {
    int s, t; cin >> s >> t;
    cin >> C[s][t];
    C[t][s] = C[s][t];
  }
  
  rep(k,N) rep(i,N) rep(j,N)
    C[i][j] = min(C[i][j], C[i][k]+C[k][j]);
  
  
  int ans = INF;
  REP(i,1,N-1) REP(j,1,N-1) {
    if(i==j) continue;
    ans = min(ans, C[0][i]+S[i]+C[i][j]+S[j]+C[j][N-1]);
  }
  
  cout << ans << endl;
  
  return 0;
}