yukicoder 0017 2つの地点に泊まりたい
問題文概要
辺と頂点に重みの付いたグラフと, 二頂点 $s$, $t$ が与えられる.
$s$, $t$ 以外の二頂点 $u$, $v$ を選んだとき, $u$, $v$ を通る $s{\rm -}t$ path に対するコストを path 上の全ての辺重みと, $u$, $v$ の頂点重みの和で定める.
$u$, $v$ をうまくえらび, コストを最小化しろ.
制約
$4 \le n \le 50$, 解がある.
解法
とりあえず Warshall-Floyd しておいて, 滞在する $2$ 点を固定した時の最小コストで更新を繰り返す. $O(n^3)$.
ソースコード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool solve(){
int n; cin >> n;
vector<int> s(n); for(aur x : s) cin >> x;
vector<vector<int>> g(n, vector<int>(n, numeric_limits<int>::max()/4));
rep(u, n) g[u][u] = 0;
{
int m; cin >> m;
rep(_, m){
int a, b, c; cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
}
rep(k, n) rep(i, n) rep(j, n) chmin(g[i][j], g[i][k] + g[k][j]);
int res = numeric_limits<int>::max();
rep(i, n) if(i != 0 and i != n-1) rep(j, n) if(j != 0 and j != n-1 and i != j)
chmin(res, s[0] + g[0][i] + s[i] + g[i][j] + s[j] + g[j][n-1] + s[n-1]);
cout << res << endl;
return true;
}