結果

問題 No.2673 A present from B
ユーザー NokonoKotlinNokonoKotlin
提出日時 2024-03-13 20:08:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 179 ms / 2,000 ms
コード長 2,851 bytes
コンパイル時間 3,773 ms
コンパイル使用メモリ 267,548 KB
実行使用メモリ 40,832 KB
最終ジャッジ日時 2024-09-29 23:35:37
合計ジャッジ時間 4,839 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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