Submission

[PP-SSSSSSSSSSSS]

Score: 0

User: qwerty

Problemset: อัศวินขี่ม้าขาว

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-17 12:48:23

#include<bits/stdc++.h>
using namespace std;

#define tup tuple<int, int, int>
int walk(vector<vector<int>> &path, vector<vector<int>> &parent, int x, int y, int n, int m){
    vector<vector<int>> dis(n+1, vector<int>(m+1, INT_MIN));
    vector<vector<bool>> visited(n+1, vector<bool>(m+1, false));
    priority_queue<tup> pq;

    dis[1][1] = path[1][1];
    // w x y
    pq.push({dis[1][1], 1, 1});
    
    while(!pq.empty()){
        int x = get<1>(pq.top());
        int y = get<2>(pq.top());
        pq.pop();
        if (x==n && y==m){
            return dis[x][y];
        }
        if (visited[x][y]) continue;
        visited[x][y] = true;

        if (x+1<=n){
            int w1 = path[x+1][y];
            if (!visited[x+1][y] && dis[x+1][y]<dis[x][y]+w1){
                dis[x+1][y] = dis[x][y]+w1;
                parent[x+1][y] = x*m+y;
                pq.push({dis[x+1][y], x+1, y});
            }
        }
        if (y+1<=m){
            int w2 = path[x][y+1];
            if (!visited[x][y+1] && dis[x][y+1]<dis[x][y]+w2){
                dis[x][y+1] = dis[x][y]+w2;
                parent[x][y+1] = x*m+y;
                pq.push({dis[x][y+1], x, y+1});
            }
        }
    }
    return dis[x][y];
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> path(n+1, vector<int>(m+1, 0));
    // start at (1, 1)
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= m ; j++){
            cin >> path[i][j];
        }
    }

    vector<vector<int>> parent(n+1, vector<int>(m+1 ,-1));
    int d = walk(path, parent, 1, 1, n, m);

    int x = n, y = m;
    vector<pair<int, int>> res;
    res.push_back({x, y});
    while (x != 1 || y != 1){
        int px = parent[x][y]/m;
        int py = parent[x][y]%m;
        res.push_back({px,py});
        x = px;
        y = py;
    }

    reverse(res.begin(), res.end());
    int minn = path[res[0].first][res[0].second];
    for (int i = 1 ; i < res.size() ; i++){
        int curr = path[res[i].first][res[i].second] + path[res[i-1].first][res[i-1].second];
        minn = min(curr, minn);
    }

    d = min(minn, d);
    // cout << d << endl;
    int ans = d*-1+1;
    cout << ans;
}