1119. Metro - Timus(primele 6 teste)

#include <bits/stdc++.h>
#define int long long
#define R2 1.414213562373

using namespace std;

const int INF = 1e18L;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M, K;
    cin >> N >> M >> K;
    vector < vector < long double > > dp(N + 1, vector < long double >(M + 1, INF)), D(N + 1, vector < long double >(M + 1, INF));
    while(K--) {
        int x, y;
        cin >> x >> y;
        D[x][y] = 100 * R2;
    }
    if(D[1][1] != INF)
        dp[1][1] = D[1][1];
    else
        dp[1][1] = 200;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            if(i != 1 || j != 1)
                dp[i][j] = min(dp[i - 1][j] + 100, min(dp[i][j - 1] + 100, dp[i - 1][j - 1] + D[i][j]));
    int ans = (int)(dp[N][M] * 10), sol = ans / 10;
    if(ans % 10 > 4)
        ++sol;
    cout << sol;
}