結果
問題 | 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 #endif using 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; }