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;
}