結果
問題 |
No.2855 Move on Grid
|
ユーザー |
![]() |
提出日時 | 2024-08-25 14:35:00 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 830 ms / 3,000 ms |
コード長 | 1,813 bytes |
コンパイル時間 | 3,220 ms |
コンパイル使用メモリ | 265,252 KB |
実行使用メモリ | 14,496 KB |
最終ジャッジ日時 | 2024-08-25 14:35:32 |
合計ジャッジ時間 | 26,931 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#define rep(i, n) for (int i = 0; i < (int)(n); i++) #define ALL(v) v.begin(), v.end() typedef long long ll; #include <bits/stdc++.h> using namespace std; template <class T> using V=vector<T>; template <class T> using VV=V<V<T>>; const ll INF=1LL<<60; struct Edge{ int to; ll w; Edge(int to,ll w) : to(to),w(w) {} }; using Graph=vector<vector<Edge>>; using pli=pair<ll,int>; template<class T> bool chmin(T& a,T b){ if(a>b){ a=b; return true; } return false; } Graph G; vector<ll> dijkstra(int s){ int n=G.size(); vector<ll> dist(n,INF); dist[s]=0; priority_queue<pli,vector<pli>,greater<pli>> que; que.push({dist[s],s}); while(!que.empty()){ int v=que.top().second; ll d=que.top().first; que.pop(); if(d>dist[v]) continue; for(auto e:G[v]){ if(chmin(dist[e.to],dist[v]+e.w)){ que.push({dist[e.to],e.to}); } } } return dist; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int n,m,k; cin>>n>>m>>k; VV<int> A(n,V<int>(m)); rep(i,n) rep(j,m) cin>>A[i][j]; int ok=0,ng=1e9+1; while(ng-ok>1){ int mid=(ok+ng)/2; G.resize(n*m); rep(i,n) rep(j,m){ int t=i*m+j; if(A[i][j]<mid){ if(j>0) G[t-1].push_back(Edge(t,1)); if(j<m-1) G[t+1].push_back(Edge(t,1)); if(i>0) G[t-m].push_back(Edge(t,1)); if(i<n-1) G[t+m].push_back(Edge(t,1)); } else{ if(j>0) G[t-1].push_back(Edge(t,0)); if(j<m-1) G[t+1].push_back(Edge(t,0)); if(i>0) G[t-m].push_back(Edge(t,0)); if(i<n-1) G[t+m].push_back(Edge(t,0)); } } auto dis=dijkstra(0); int tmp=dis[n*m-1]; if(A[0][0]<mid) tmp++; if(tmp<=k) ok=mid; else ng=mid; G.resize(0); } cout<<ok<<endl; return 0; }