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