Advertisement
YEZAELP

PROG-1149: บีคุนบันคุง (2Bk)

Jul 11th, 2020
88
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 2e9;
  5. using pii = pair < int,pair<int,int> >;
  6. int ar[1001][1001];
  7. int ki[5] = {0,0,0,1,-1}, kj[5] = {0,1,-1,0,0};
  8. int n;
  9.  
  10. int main(){
  11.  
  12.     scanf("%d",&n);
  13.     int ar[n+1][n+1];
  14.     long long dis[n+1][n+1];
  15.     bool visited[n+1][n+1];
  16.     int si=-1,sj=-1,ei=-1,ej=-1,mx=0;
  17.     for(int i=1;i<=n;i++){
  18.         for(int j=1;j<=n;j++){
  19.             dis[i][j] = INF;
  20.             visited[i][j] = false;
  21.  
  22.             scanf("%d",&ar[i][j]);
  23.             if(ar[i][j] == 0){
  24.                 if(si == -1&&sj == -1){
  25.                     si = i;
  26.                     sj = j;
  27.                 }
  28.                 else {
  29.                     ei = i;
  30.                     ej = j;
  31.                 }
  32.             }
  33.         }
  34.     }
  35.  
  36.     priority_queue < pii , vector<pii> , greater<pii> > pq;
  37.     dis[si][sj] = 0;
  38.     pq.push({ 0 , {si,sj} });
  39.  
  40.     while(pq.size()>0){
  41.         int ui,uj;
  42.         ui = pq.top().second.first;
  43.         uj = pq.top().second.second;
  44.         pq.pop();
  45.  
  46.         visited[ui][uj] = true;
  47.  
  48.         if(ar[ui][uj]>mx) mx = ar[ui][uj];
  49.         if(ui == ei && uj == ej){
  50.             printf("%d",mx);
  51.             break;
  52.         }
  53.  
  54.         for(int k=1;k<=4;k++){
  55.             if(ui+ki[k]>=1 && ui+ki[k]<=n && uj+kj[k]>=1 && uj+kj[k]<=n && visited[ui+ki[k]][uj+kj[k]]==false && dis[ui][uj]+ar[ui+ki[k]][uj+kj[k]]<dis[ui+ki[k]][uj+kj[k]] ){
  56.                 dis[ui+ki[k]][uj+kj[k]]= dis[ui][uj]+ar[ui][uj];
  57.                 pq.push({ar[ui+ki[k]][uj+kj[k]] ,{ui+ki[k],uj+kj[k]} });
  58.             }
  59.         }
  60.  
  61.     }
  62.  
  63.  
  64.  
  65.     return 0;
  66. }
Advertisement
RAW Paste Data Copied
Advertisement