Advertisement
YEZAELP

o56_oct_c2_forest

Jan 15th, 2022
885
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int inf = 1e9;
  5. using pi = pair <int, int>;
  6. using pii = pair <pi, pi>;
  7. const int maxN = 20 + 10;
  8. const int maxP = 20 + 10;
  9. vector <pi> sg[maxN][maxN];
  10. int w[maxN][maxN], dis[maxN][maxN][maxP];
  11. bool vs[maxN][maxN][maxP];
  12. pi in[maxP], out[maxP];
  13. int di[] = {0, 0, 1, -1}, dj[] = {1, -1, 0, 0};
  14. int N, K, P;
  15.  
  16. bool pst(int ui, int uj){
  17.     return 1 <= ui and ui <= N and 1 <= uj and uj <= N;
  18. }
  19.  
  20. int main(){
  21.  
  22.     scanf("%d %d %d", &N, &P, &K);
  23.  
  24.     for(int i=1;i<=N;i++){
  25.         for(int j=1;j<=N;j++){
  26.             scanf("%d", &w[i][j]);
  27.         }
  28.     }
  29.  
  30.     for(int i=1;i<=P;i++){
  31.         int si, sj, ei, ej;
  32.         scanf("%d %d %d %d", &si, &sj, &ei, &ej);
  33.         si ++, sj ++, ei ++, ej ++;
  34.         sg[si][sj].push_back({ei, ej});
  35.     }
  36.  
  37.     for(int i=0;i<=N;i++){
  38.         for(int j=0;j<=N;j++){
  39.             for(int k=0;k<=K;k++){
  40.                 dis[i][j][k] = inf;
  41.                 vs[i][j][k] = false;
  42.             }
  43.         }
  44.     }
  45.  
  46.     priority_queue <pii, vector <pii>, greater <pii>> pq;
  47.     dis[1][1][0] = 0;
  48.     pq.push({ {dis[1][1][0], 0} , {1, 1} });
  49.  
  50.     while(!pq.empty()){
  51.         int d = pq.top().first.first;
  52.         int k = pq.top().first.second;
  53.         int ui = pq.top().second.first;
  54.         int uj = pq.top().second.second;
  55.         pq.pop();
  56.         if(vs[ui][uj][k]) continue;
  57.         vs[ui][uj][k] = true;
  58.         if(ui == N and uj == N){
  59.             printf("%d", d);
  60.             return 0;
  61.         }
  62.         for(int dij=0;dij<4;dij++){
  63.             int vi = ui + di[dij];
  64.             int vj = uj + dj[dij];
  65.             if(pst(vi, vj) and !vs[vi][vj][k] and d + w[vi][vj] < dis[vi][vj][k]){
  66.                 dis[vi][vj][k] = d + w[vi][vj];
  67.                 pq.push({ {dis[vi][vj][k], k} , {vi, vj} });
  68.             }
  69.         }
  70.         if(k < K){
  71.             for(auto vij: sg[ui][uj]){
  72.                 int vi = vij.first;
  73.                 int vj = vij.second;
  74.                 if(!vs[vi][vj][k + 1] and d < dis[vi][vj][k + 1]){
  75.                     dis[vi][vj][k + 1] = d;
  76.                     pq.push({ {dis[vi][vj][k + 1], k + 1} , {vi, vj} });
  77.                 }
  78.             }
  79.         }
  80.     }
  81.  
  82.     return 0;
  83. }
Advertisement
RAW Paste Data Copied
Advertisement