結果

問題 No.788 トラックの移動
コンテスト
ユーザー 梧桐
提出日時 2026-01-27 00:10:43
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 419 ms / 2,000 ms
コード長 1,775 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 906 ms
コンパイル使用メモリ 96,512 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-01-27 00:10:47
合計ジャッジ時間 3,946 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void Dijkstra(int)’:
main.cpp:31:14: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   31 |         auto [dist, pos] = pq.top(); pq.pop();
      |              ^

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2010, M = N * 2, INF = 2000000010;

int n, m, st, ttl, a[N], rt_d[N], d[N];
int h[N], e[M], w[M], ne[M], idx;
priority_queue<PII, vector<PII>, greater<PII>> pq;
bool vis[N];
LL v1, v2, ans;

void Add(int x, int y, int z) {
    e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}

void Dijkstra(int u) {
    fill(d + 1, d + n + 1, INF);
    memset(vis, 0, sizeof(vis));

    d[u] = 0;
    pq.push({ d[u], u });
    while (!pq.empty()) {
        auto [dist, pos] = pq.top(); pq.pop();
        if (vis[pos]) continue;
        vis[pos] = true;
        for (int i = h[pos]; i != -1; i = ne[i]) {
            int j = e[i], k = w[i];
            if (dist + k < d[j]) {
                d[j] = dist + k;
                pq.push({ d[j], j });
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &st);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        if (a[i]) ++ttl;
    }
    memset(h, -1, sizeof(h));
    for (int i = 1, x, y, z; i <= m; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        Add(x, y, z), Add(y, x, z);
    }

    Dijkstra(st);
    memcpy(rt_d, d, sizeof(d));

    // x 为聚集点
    ans = 9e18;
    for (int x = 1; x <= n; ++x) {
        Dijkstra(x);
        v1 = 0LL;
        for (int i = 1; i <= n; ++i) {
            v1 += 1LL * d[i] * a[i];
        }
        v2 = 9e18;
        for (int i = 1; i <= n; ++i) {
            if (a[i]) {
                v2 = min(v2, 0LL + rt_d[i] - d[i]);
            }
        }
        ans = min(ans, v1 * 2 + (x == st ? 0LL : v2));
    }
    printf("%lld\n", ttl <= 1 ? 0 : ans);

    return 0;
}
0