Problem 70: Minimum Path Sum in Grid with Teleports

Problem Statement: Given a grid with non-negative weights and several teleportation pairs connecting specific cells, compute the minimum path sum from the top-left to bottom-right cell. Moves are allowed right and down, plus teleportation between given pairs with no cost.

Input

The first line contains two integers n and m. Then n lines follow with m integers each representing the grid weights. Next is an integer t, the number of teleport pairs, followed by t lines each with four integers r1, c1, r2, c2 indicating a teleport from (r1,c1) to (r2,c2).

Output

Print the minimum path sum from (1,1) to (n,m).

Examples


Input:
3 3
1 3 1
1 5 1
4 2 1
1
2 2 3 1

Output:
7

Solution Explanation

Use Dijkstra's algorithm on a graph where each cell is a node. Add edges for right and down moves with corresponding weights, and add zero cost edges for teleports.

Solution in C++


#include 
#include 
#include 
#include 
using namespace std;

int main(){
    int n, m; 
    cin >> n >> m;
    vector> grid(n, vector(m));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> grid[i][j];
    int t; 
    cin >> t;
    vector>> teleports(n * m);
    auto idx = [&](int r, int c){ return r * m + c; };
    for(int i = 0; i < t; i++){
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        r1--; c1--; r2--; c2--;
        teleports[idx(r1, c1)].push_back({r2, c2});
    }
    const int INF = 1000000000;
    vector dist(n * m, INF);
    priority_queue, vector>, greater>> pq;
    dist[0] = grid[0][0];
    pq.push({dist[0], 0});
    int dr[2] = {0, 1}, dc[2] = {1, 0};
    while(!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();
        if(d != dist[u]) continue;
        int r = u / m, c = u % m;
        for(int i = 0; i < 2; i++){
            int nr = r + dr[i], nc = c + dc[i];
            if(nr < n && nc < m){
                int v = idx(nr, nc);
                if(dist[v] > d + grid[nr][nc]){
                    dist[v] = d + grid[nr][nc];
                    pq.push({dist[v], v});
                }
            }
        }
        for(auto &p : teleports[u]){
            int v = idx(p.first, p.second);
            if(dist[v] > d){
                dist[v] = d;
                pq.push({dist[v], v});
            }
        }
    }
    cout << dist[n * m - 1] << "\n";
    return 0;
}