結果
問題 | No.2673 A present from B |
ユーザー |
👑 ![]() |
提出日時 | 2024-02-09 18:14:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 187 ms / 2,000 ms |
コード長 | 3,458 bytes |
コンパイル時間 | 2,387 ms |
コンパイル使用メモリ | 211,300 KB |
最終ジャッジ日時 | 2025-02-19 03:03:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#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" : " ");}}