Yukicoder017 2つの地点に泊まりたい

問題概要

$0$ から$N−1$までの$N$個の地点がある。 地点から地点の移動コストが$M$個、$edge(a,b)=c$が与えられる。 また各地点に滞在コスト$S[i]$がある。

$0$地点から$N−1$地点にたどり着くまでに、 $0$地点と$N−1$地点以外の異なる2つの地点に滞在しなければならない。 滞在する地点は自由に決めて良い。 この条件での移動コストと滞在コストの合計の最小値を求めよ。

都市を通るけど、滞在しないこともできます。

$N\leqq50$、$M\leqq N^2$、$S[i],edge(a,b)\leqq10^3$

yukicoder017

解法

2点よりも多い点に移動しても滞在するのはダメなので二点をきめると3つの最短路の合計値がコストの合計になる。 全点間の最短距離はワーシャルフロイド法で求めることができる。 これの最小値を求めるときに全探索をすればよい。

計算量:$O(M+N^3)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e16;
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI s(N);
        FOR(i, 0, N) {
            cin >> s[i];
        }
        int M; cin >> M;
        VVI d(N, VI(N, INF));
        FOR(i, 0, N)d[i][i] = 0;
        FOR(i, 0, M) {
            int a, b, c;
            cin >> a >> b >> c;
            d[a][b] = d[b][a] = c;
        }
        FOR(k, 0, N)FOR(i, 0, N)FOR(j, 0, N) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
        ans = INF;
        FOR(i, 1, N - 1) {
            FOR(j, 1, N - 1) {
                if (i != j)
                    ans = min(ans, (LL)d[0][i] + d[i][j] + d[j][N - 1] + s[i] + s[j]);
            }
        }
        cout << ans << "\n";
    
        return 0;
    }