トラックの移動 [yukicoder No.788] - はまやんはまやんはまやん

前提知識

ダイクストラ

考察過程

1. かなり難しい問題に見えるので、小さいことから紐解いていく
2. M≦2000が気になる（普通なら10^6くらいじゃない？）
3. この制約なら、全ての頂点間の距離を求められる
4. とりあえず何か全探索対象を探すが、集める交差点が全探索できそう（Nが10^3オーダーなので想定の匂いもする）
5. 他に考える糸口も無いので、集める所pを固定したときの最適解について考えてみる
6. すると、集める所p以外の場所は頂点stにあるトラックを集めるにはT[st]回往復する必要があり、簡単に移動距離を求められそう
7. ただし、最初にLにいて、「寄り道せず頂点pに行く」「ある頂点の荷物を回収してから頂点pに行く」の2通り考えられる
8. 寄り道も全探索できるか？
9. できる

解説

https://yukicoder.me/submissions/315638

コーナーケースとして、もともと1つの頂点にトラックが集まっている場合は0が答え。
　
まずは、全頂点間の距離を求めよう。
M≦2000なので、各頂点についてダイクストラをすれば求められる。
　
次にトラックを集める頂点pと、最初に頂点Lから寄り道する頂点stを全探索して最適解を選ぼう。
この時点で計算量4*10^6なので、答えを高速に求める必要がある。
そのために、頂点pにレッカーが最初いて、そこから全ての頂点のトラックを集めるのにかかる移動距離を前計算しておこう（変数base）
すると、最初に頂点stに寄り道した場合は、baseからその頂点にトラックを1つ取りに行く移動距離が必要無くなるので、
D[L][st] + D[st][p] + base - D[p][st] * 2
がその時の移動距離になる。
この移動距離の最小値が答え。

int N, M, L, T[2010];
vector<pair<int, int>> E[2010];
vector<ll> D[2010];
//---------------------------------------------------------------------------------------------------
int vis[101010];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
void dijk(int s, vector<ll> &D) {
    D.resize(N);
    rep(i, 0, N) D[i] = infl;
    rep(i, 0, N) vis[i] = 0;

    min_priority_queue<pair<ll, int>> que;

    D[s] = 0;
    que.push({ 0, s });

    while (!que.empty()) {
        auto q = que.top(); que.pop();

        ll cst = q.first;
        int cu = q.second;

        if (vis[cu]) continue;
        vis[cu] = 1;

        fore(p, E[cu]) {
            ll cst2 = cst + p.second;
            int to = p.first;

            if (chmin(D[to], cst2)) que.push({ D[to], to });
        }
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> L; L--;
    rep(i, 0, N) cin >> T[i];
    rep(i, 0, M) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        E[a].push_back({ b,c });
        E[b].push_back({ a,c });
    }

    int cnt = 0;
    rep(i, 0, N) if (0 < T[i]) cnt++;
    if (cnt <= 1) {
        printf("0\n");
        return;
    }

    rep(i, 0, N) dijk(i, D[i]);

    ll ans = infl;
    rep(p, 0, N) {
        ll base = 0;
        rep(i, 0, N) base += T[i] * D[p][i] * 2;
        rep(st, 0, N) if(T[st]) {
            ll sm = D[L][st] + D[st][p];
            ll cand = base - D[p][st] * 2 + sm;
            chmin(ans, cand);
        }
    }
    cout << ans << endl;
}