Участник:Andriygav/ADAHOSE

Материал из DISCOPAL
Перейти к: навигация, поиск
  • компилятор: gcc 8.3
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
 
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
 
int dis[1024*1024];
int A[1024][1024];
 
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> A[i][j];
        }
    }
    for (int i = 0; i <= n*n; i++){
        dis[i] = 1073741824;
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
 
    dis[n * n] = 0;
 
    pq.emplace(0, n*n);
    while(!pq.empty()){
        auto now = pq.top();
        pq.pop();
        if (dis[now.second] < now.first){
            continue;
        }
        if(now.second == n*n){
            for(int i = 0; i < n; ++i){
                int cost = now.first + A[i][0];
                int next = i*n;
                if(dis[next] > cost){
                    dis[next] = cost;
                    pq.emplace(cost, next);
                }
            }
        }else{
            int d = now.second / n;
            int r = now.second % n;
            for(int i = 0; i < 4; i++){
                int dd = d + dx[i];
                int dr = r + dy[i];
                if(dd < 0 || dd >= n || dr < 0 || dr >= n){
                    continue;
                }
                int next = dd*n + dr;
                int cost = A[d][r] + A[dd][dr] + now.first;
                if(dis[next] > cost){
                    dis[next] = cost;
                    pq.emplace(cost, next);
                }
            }
        }
    }
    int ret = 1073741824;
    for(int i = 0; i < n; i++){
        ret = min(ret, dis[i*n + n - 1] + A[i][n - 1]);
    }
    cout << ret;
    return 0;
}