結果

問題 No.2673 A present from B
ユーザー nu50218nu50218
提出日時 2024-03-13 22:38:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 175 ms / 2,000 ms
コード長 2,849 bytes
コンパイル時間 2,571 ms
コンパイル使用メモリ 219,184 KB
実行使用メモリ 40,704 KB
最終ジャッジ日時 2024-09-29 23:38:47
合計ジャッジ時間 4,166 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 175 ms
40,704 KB
testcase_07 AC 164 ms
40,704 KB
testcase_08 AC 172 ms
40,576 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 34 ms
14,080 KB
testcase_13 AC 35 ms
13,952 KB
testcase_14 AC 63 ms
20,736 KB
testcase_15 AC 19 ms
9,344 KB
testcase_16 AC 18 ms
9,216 KB
testcase_17 AC 12 ms
7,040 KB
testcase_18 AC 21 ms
9,984 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 49 ms
17,664 KB
testcase_21 AC 119 ms
32,256 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 1 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

struct edge {
    pair<int, int> to;
    int w;
    edge() : to(make_pair(0, 0)), w(0) {}
    edge(pair<int, int> to, int w) : to(to), w(w) {}
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
        a[i]--;
    }

    // (2M + 1) × N 頂点の有向グラフを構築する
    // 元のあみだくじの横線が *** 、縦線が |
    // 便宜上追加する横向きの辺が --- （ここにあみだくじの横線を追加できる）
    // しかし、実際は元のあみだくじの線 *** はクロスして張る
    //
    // サンプル2のときに構築するグラフ
    //   0   1   2   3
    // 0 |---|---|---|
    // 1 |***|   |   |
    // 2 |---|---|---|
    // 3 |   |***|   |
    // 4 |---|---|---|
    // 5 |   |   |***|
    // 6 |---|---|---|
    //
    // g[i][j] 上からi番目左からj番目の頂点
    vector g(2 * m + 1, vector(n, vector<edge>(0)));

    // 便宜上追加する横線
    for (int i = 0; i < 2 * m + 1; i++) {
        if (i % 2 == 0) {
            for (int j = 0; j < n; j++) {
                if (0 <= j - 1) g[i][j].push_back(edge({i, j - 1}, 1));
                if (j + 1 < n) g[i][j].push_back(edge({i, j + 1}, 1));
            }
        }
    }

    // 縦線
    for (int i = 0; i < 2 * m + 1; i++) {
        for (int j = 0; j < n; j++) {
            if (i - 1 >= 0) {
                // あみだくじの線をクロスさせる
                if (i % 2 == 1 and j == a[i / 2]) {
                    g[i][j].push_back(edge({i - 1, j + 1}, 0));
                    g[i][j + 1].push_back(edge({i - 1, j}, 0));
                    j++;
                } else {
                    g[i][j].push_back(edge({i - 1, j}, 0));
                }
            }
        }
    }

    // g[2 * m][0]からの最短経路をダイクストラ法で求める
    vector dist(2 * m + 1, vector<int>(n, INF));
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
    q.push({0, {2 * m, 0}});
    dist[2 * m][0] = 0;
    while (!q.empty()) {
        auto [tmp_dist, tmp_e] = q.top();
        int tmp_row = tmp_e.first;
        int tmp_clm = tmp_e.second;
        q.pop();

        if (dist[tmp_row][tmp_clm] < tmp_dist) continue;

        for (auto&& [next_e, weight] : g[tmp_row][tmp_clm]) {
            auto [next_row, next_clm] = next_e;
            if (dist[next_row][next_clm] > dist[tmp_row][tmp_clm] + weight) {
                dist[next_row][next_clm] = dist[tmp_row][tmp_clm] + weight;
                q.push({dist[next_row][next_clm], next_e});
            }
        }
    }

    for (int i = 1; i < n; i++) {
        cout << dist[0][i] << (i == n - 1 ? "\n" : " ");
    }
}
0