o56_oct_c2_forest

#include <bits/stdc++.h>

using namespace std;
const int inf = 1e9;
using pi = pair <int, int>;
using pii = pair <pi, pi>;
const int maxN = 20 + 10;
const int maxP = 20 + 10;
vector <pi> sg[maxN][maxN];
int w[maxN][maxN], dis[maxN][maxN][maxP];
bool vs[maxN][maxN][maxP];
pi in[maxP], out[maxP];
int di[] = {0, 0, 1, -1}, dj[] = {1, -1, 0, 0};
int N, K, P;

bool pst(int ui, int uj){
    return 1 <= ui and ui <= N and 1 <= uj and uj <= N;
}

int main(){

    scanf("%d %d %d", &N, &P, &K);

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            scanf("%d", &w[i][j]);
        }
    }

    for(int i=1;i<=P;i++){
        int si, sj, ei, ej;
        scanf("%d %d %d %d", &si, &sj, &ei, &ej);
        si ++, sj ++, ei ++, ej ++;
        sg[si][sj].push_back({ei, ej});
    }

    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            for(int k=0;k<=K;k++){
                dis[i][j][k] = inf;
                vs[i][j][k] = false;
            }
        }
    }

    priority_queue <pii, vector <pii>, greater <pii>> pq;
    dis[1][1][0] = 0;
    pq.push({ {dis[1][1][0], 0} , {1, 1} });

    while(!pq.empty()){
        int d = pq.top().first.first;
        int k = pq.top().first.second;
        int ui = pq.top().second.first;
        int uj = pq.top().second.second;
        pq.pop();
        if(vs[ui][uj][k]) continue;
        vs[ui][uj][k] = true;
        if(ui == N and uj == N){
            printf("%d", d);
            return 0;
        }
        for(int dij=0;dij<4;dij++){
            int vi = ui + di[dij];
            int vj = uj + dj[dij];
            if(pst(vi, vj) and !vs[vi][vj][k] and d + w[vi][vj] < dis[vi][vj][k]){
                dis[vi][vj][k] = d + w[vi][vj];
                pq.push({ {dis[vi][vj][k], k} , {vi, vj} });
            }
        }
        if(k < K){
            for(auto vij: sg[ui][uj]){
                int vi = vij.first;
                int vj = vij.second;
                if(!vs[vi][vj][k + 1] and d < dis[vi][vj][k + 1]){
                    dis[vi][vj][k + 1] = d;
                    pq.push({ {dis[vi][vj][k + 1], k + 1} , {vi, vj} });
                }
            }
        }
    }

    return 0;
}