結果
問題 | No.2673 A present from B |
ユーザー |
![]() |
提出日時 | 2024-03-15 22:52:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,778 ms / 2,000 ms |
コード長 | 1,123 bytes |
コンパイル時間 | 2,041 ms |
コンパイル使用メモリ | 203,396 KB |
最終ジャッジ日時 | 2025-02-20 05:48:29 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
/*** author: t9unkubj* created: 2024-03-15*/#include<bits/stdc++.h>#ifdef t9unkubj#define _GLIBCXX_DEBUG#define dbg(x) cout<<__LINE__<<" "<<#x<<":="<<x<<endl;#else#define dbg(x) 58#endifusing namespace std;//#include<atcoder/all>//using namespace atcoder;int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);int n,m;cin>>n>>m;vector<int>a(m);for(int i=0;i<m;i++)cin>>a[i],a[i]--;vector<vector<pair<int,int>>>g(n*(m+1));for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(j==a[i])g[i*n+n+j+1].push_back({i*n+j,0});else if(j==a[i]+1)g[i*n+n+j-1].push_back({i*n+j,0});else g[i*n+n+j].push_back({i*n+j,0});}}using T=pair<int,int>;priority_queue<T,vector<T>,greater<T>>que;vector<int>md(n*(m+1),1<<30);md[n*m]=0;que.push({0,n*m});while(que.size()){auto [p,q]=que.top();que.pop();if(p!=md[q])continue;for(auto [x,w]:g[q]){if(md[x]>p+w)md[x]=p+w,que.push({md[x],x});}for(int i=q/n*n;i<q/n*(n)+n;i++){dbg(i);if(md[i]>p+abs((i)-q))md[i]=p+abs((i)-q),que.push({md[i],i});}}for(int i=1;i<n;i++)cout<<md[i]<<" ";cout<<endl;}