taxe2

#include <bits/stdc++.h>

using namespace std;

ifstream fin("taxe2.in");
ofstream fout("taxe2.out");

int S, n, a[105][105], s[105][105];
int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};
bitset<105> v[105];

struct taxa
{
    int suma, i, j;
};

struct comparator
{
    bool operator()(const taxa &t1, const taxa &t2)
    {
        return t1.suma < t2.suma;
        //return s[t1.i][t1.j] < s[t2.i][t2.j];
    }
};

bool corect(int i, int j)
{
    return i >= 1 && j >= 1 && i <= n && j <= n;
}

void lee(int i, int j)
{
    s[i][j] = a[i][j]; /// suma din punctul de plecare este evident suma de din punctul din care pornim

    priority_queue<taxa, vector<taxa>, comparator> q; /// creez o coada cu prioritati pentru a memora cea mai buna suma cat si indici aceste sume
    q.push({-s[i][j], i, j});                         /// in coada pun suma cu - pentru a avea mereu cea mai mica suma in .top()
    v[i][j] = 1;                                      /// am suma in coada deci o marchez

    while (!q.empty())
    {
        int suma = -q.top().suma;
        i = q.top().i;
        j = q.top().j;
        q.pop();

        v[i][j] = 0; /// debifez suma pentru a o putea inlocui daca este cazul alta data

        for (int k = 0; k < 4; k++) /// iau fiecare vecin al sumei curente
        {
            int ni = i + di[k];
            int nj = j + dj[k];
            if (corect(ni, nj) && a[ni][nj] + suma < s[ni][nj]) /// daca o pot imbunatatii
            /// adica daca suma curenta + elementul urmator este mai < decat suma urmatoare
            {
                s[ni][nj] = suma + a[ni][nj]; /// actualizez suma
                if (!v[ni][nj])               /// daca punctul nu a fost adaugat in coada il pun
                    q.push({-s[ni][nj], ni, nj}), v[ni][nj] = 1;
            }
        }
    }
}

int main()
{
    fin >> S >> n; /// citest suma maxima si matricea
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            fin >> a[i][j];

    memset(s, 1, sizeof(s)); /// setez toate elemntele matricei de sume cu infinit
    /// pentru a putea retine mai tarziu sumele minime
    /// daca toate elementele ar fi 0 si suma minima ar fi 0!!

    lee(1, 1); /// pornesc din coltul din stanga sus

    if (s[n][n] <= S) /// daca suma de bani cu care am ajuns in dreapta jos imi ajunge
        fout << S - s[n][n];
    else
        fout << -1;

    fin.close();
    fout.close();

    return 0;
}