結果

問題 No.2673 A present from B
ユーザー 👑 eoeo
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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] ij
// ***
//
// 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" : " ");
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0