結果

問題 No.2673 A present from B
ユーザー 👑 eoeoeoeo
提出日時 2024-02-09 18:14:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 3,458 bytes
コンパイル時間 2,866 ms
コンパイル使用メモリ 220,628 KB
実行使用メモリ 40,832 KB
最終ジャッジ日時 2024-03-13 21:50:29
合計ジャッジ時間 5,120 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 169 ms
40,832 KB
testcase_07 AC 169 ms
40,832 KB
testcase_08 AC 167 ms
40,832 KB
testcase_09 AC 2 ms
6,676 KB
testcase_10 AC 3 ms
6,676 KB
testcase_11 AC 2 ms
6,676 KB
testcase_12 AC 39 ms
14,080 KB
testcase_13 AC 44 ms
14,080 KB
testcase_14 AC 68 ms
20,864 KB
testcase_15 AC 22 ms
9,472 KB
testcase_16 AC 21 ms
9,344 KB
testcase_17 AC 14 ms
7,168 KB
testcase_18 AC 24 ms
10,112 KB
testcase_19 AC 2 ms
6,676 KB
testcase_20 AC 53 ms
17,792 KB
testcase_21 AC 127 ms
32,384 KB
testcase_22 AC 2 ms
6,676 KB
testcase_23 AC 2 ms
6,676 KB
testcase_24 AC 2 ms
6,676 KB
testcase_25 AC 2 ms
6,676 KB
testcase_26 AC 2 ms
6,676 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 頂点の無向グラフを張る
    // 元のあみだくじの線が*** 便宜上追加する辺が---
    // g[i][j] 上からi番目左からj番目の頂点
    // しかし、実際は元のあみだくじの線 *** はクロスして張る
    //
    //   0   1   2   3
    // 0 |---|---|---|
    // 1 |***|   |   |
    // 2 |---|---|---|
    // 3 |   |***|   |
    // 4 |---|---|---|
    // 5 |   |   |***|
    // 6 |---|---|---|

    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));
                }
            }
        }
    }

    // 元からあるあみだくじの横線
    // for (int i = 0; i < m; i++) {
    //     int x = a[i];
    //     int j = 2 * i + 1;
    //     g[j][x].push_back(edge({j, x + 1}, 0));
    //     g[j][x + 1].push_back(edge({j, x}, 0));
    // }

    // デバッグ用の出力
    // for (int i = 0; i < 2 * m + 1; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << i << " " << j << endl;
    //         for (auto&& e : g[i][j]) {
    //             cout << e.to.first << " " << e.to.second << " " << e.w << endl;
    //         }
    //     }
    // }

    // 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 (auto&& v : dist) {
    //     for (auto&& vi : v) {
    //         cout << vi << " ";
    //     }
    //     cout << endl;
    // }

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