从格点最短路模型谈起
模型
给定 (n imes n) 的格点，每个点带一个点权，允许向上下左右四个方向走，要求从 ((0, 0)) 到 ((n - 1, n - 1)) 的最短距离（点权和最小）
(DP) 的困境
对于当前点 ((i, j))，可以由四个方向转移进来，然而在进行状态转移时，下面的位置 (dp[i + 1, j]) 还未做好决策，因此不满足无后效性，所以 (dp) 无法解决此模型
(Uniform cost search)
考虑用 (bfs) 结合 (priority queue) 实现，即 (UCS) 算法
注意，节点 (i) 只有在出队时，即离开 (close) 表时，才标记其为已访问，即加入 (open) 表
struct node
{
int x, y, w;
node() {}
node(int _x, int _y, int _w): x(_x), y(_y), w(_w) {}
bool operator < (const node& A) const {return w > A.w;}
};
class Solution1 // uniform cost search
{
public:
bool check(int x, int y, int n);
int uniformCostSearch(int n, vector<vector<int>>& cost);
int exe(int n, vector<vector<int>>& cost);
};
bool Solution1::check(int x, int y, int n)
{
return x >=0 && x < n && y >= 0 && y < n;
}
int Solution1::uniformCostSearch(int n, vector<vector<int>>& cost)
{
int vis[n][n];
memset(vis, 0, sizeof(vis));
priority_queue<node> pq;
pq.push(node(0, 0, cost[0][0]));
while(!pq.empty()) {
node temp = pq.top(); pq.pop();
if(temp.x == n - 1 && temp.y == n - 1) return temp.w;
if(!vis[temp.x][temp.y]) {
vis[temp.x][temp.y] = 1;
for(int k = 0; k < 4; ++k) {
int tx = temp.x + DX[k], ty = temp.y + DY[k];
if(!vis[tx][ty] && check(tx, ty, n))
pq.push(node(tx, ty, temp.w + cost[tx][ty]));
}
}
}
return 0;
}
int Solution1::exe(int n, vector<vector<int>>& cost)
{
return uniformCostSearch(n, cost);
}
图论建模后 (dijkstra)
考虑图论建模，对于每一个点 ((i, j))，可以与 ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)) 连边，边权为 (cost[i - 1, j], cost[i + 1, j], cost[i, j - 1], cost[i, j + 1])，并且将 ((i, j)) 映射为 (i imes n + j)，随后在新的图上跑 (dijkstra)，最后统计答案时需要加上 (cost[0, 0])
为了打印路径，在每次决策时，用 (pre) 数组记录前继 ((predecessor))，逆序打印即可
class Solution2 // graph modeling + Dijkstra
{
public:
Solution2();
bool check(int x, int y, int n);
void graphModeling(int n, vector<vector<int>>& cost);
void printNewGraph(int n);
int dijkstra(int s, int t, int n, int cost);
int getShortestPath(int n, vector<vector<int>>& cost);
void printShortestPath(int s, int t);
private:
vector<pii> g[N];
int pre[N], dis[N], vis[N];
unordered_map<int, pii> mp;
};
Solution2::Solution2()
{
memset(pre, 0, sizeof(pre));
memset(dis, inf, sizeof(dis));
memset(vis, 0, sizeof(vis));
mp.clear();
}
bool Solution2::check(int x, int y, int n)
{
return x >= 0 && x < n && y >= 0 && y < n;
}
void Solution2::graphModeling(int n, vector<vector<int>>& cost)
{
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
mp[i * n + j] = pii {i, j};
for(int k = 0; k < 4; ++k) {
int tx = i + DX[k], ty = j + DY[k];
if(check(tx, ty, n)) g[i * n + j].pb(pii {tx * n + ty, cost[tx][ty]});
}
}
}
}
void Solution2::printNewGraph(int n)
{
/*Print the new graph*/
cout << "The new graph is as follows" << endl;
for(int i = 0; i < n * n; ++i) {
cout << i << ": ";
for(auto j: g[i]) cout << "(" << j.fi << ", " << j.se << ") ";
puts("");
}
puts("");
}
int Solution2::dijkstra(int s, int t, int n, int cost)
{
dis[s] = 0; vis[s] = 1;
for(int i = 0; i < n * n; ++i){
int mini = inf, u = 0;
for(int j = 0; j < n * n; ++j)
if(!vis[j] && dis[j] < mini) mini = dis[j], u = j;
vis[u] = 1;
for(auto i: g[u]){
if(!vis[i.fi] && dis[u] + i.se < dis[i.fi]) {
dis[i.fi] = min(dis[i.fi], dis[u] + i.se); // handle multiple edges
pre[i.fi] = u; // record the predecessor
}
}
}
return cost + dis[t];
}
int Solution2::getShortestPath(int n, vector<vector<int>>& cost)
{
graphModeling(n, cost);
int ans = dijkstra(0, n * n - 1, n, cost[0][0]);
return ans;
}
void Solution2::printShortestPath(int s, int t)
{
stack<int> sta;
sta.push(t);
while(1) {
int q = sta.top();
sta.push(pre[q]);
if(pre[q] == 0) break;
}
while(!sta.empty()) {
cout << mp[sta.top()].fi << ' ' << mp[sta.top()].se << endl;
sta.pop();
}
}
整体代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 1e3 + 7;
const int DX[] = {0, 1, 0, -1};
const int DY[] = {1, 0, -1, 0};
struct node
{
int x, y, w;
node() {}
node(int _x, int _y, int _w): x(_x), y(_y), w(_w) {}
bool operator < (const node& A) const {return w > A.w;}
};
class Solution1 // uniform cost search
{
public:
bool check(int x, int y, int n);
int uniformCostSearch(int n, vector<vector<int>>& cost);
int exe(int n, vector<vector<int>>& cost);
};
bool Solution1::check(int x, int y, int n)
{
return x >=0 && x < n && y >= 0 && y < n;
}
int Solution1::uniformCostSearch(int n, vector<vector<int>>& cost)
{
int vis[n][n];
memset(vis, 0, sizeof(vis));
priority_queue<node> pq;
pq.push(node(0, 0, cost[0][0]));
while(!pq.empty()) {
node temp = pq.top(); pq.pop();
if(temp.x == n - 1 && temp.y == n - 1) return temp.w;
if(!vis[temp.x][temp.y]) {
vis[temp.x][temp.y] = 1;
for(int k = 0; k < 4; ++k) {
int tx = temp.x + DX[k], ty = temp.y + DY[k];
if(!vis[tx][ty] && check(tx, ty, n))
pq.push(node(tx, ty, temp.w + cost[tx][ty]));
}
}
}
return 0;
}
int Solution1::exe(int n, vector<vector<int>>& cost)
{
return uniformCostSearch(n, cost);
}
class Solution2 // graph modeling + Dijkstra
{
public:
Solution2();
bool check(int x, int y, int n);
void graphModeling(int n, vector<vector<int>>& cost);
void printNewGraph(int n);
int dijkstra(int s, int t, int n, int cost);
int getShortestPath(int n, vector<vector<int>>& cost);
void printShortestPath(int s, int t);
private:
vector<pii> g[N];
int pre[N], dis[N], vis[N];
unordered_map<int, pii> mp;
};
Solution2::Solution2()
{
memset(pre, 0, sizeof(pre));
memset(dis, inf, sizeof(dis));
memset(vis, 0, sizeof(vis));
mp.clear();
}
bool Solution2::check(int x, int y, int n)
{
return x >= 0 && x < n && y >= 0 && y < n;
}
void Solution2::graphModeling(int n, vector<vector<int>>& cost)
{
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
mp[i * n + j] = pii {i, j};
for(int k = 0; k < 4; ++k) {
int tx = i + DX[k], ty = j + DY[k];
if(check(tx, ty, n)) g[i * n + j].pb(pii {tx * n + ty, cost[tx][ty]});
}
}
}
}
void Solution2::printNewGraph(int n)
{
/*Print the new graph*/
cout << "The new graph is as follows" << endl;
for(int i = 0; i < n * n; ++i) {
cout << i << ": ";
for(auto j: g[i]) cout << "(" << j.fi << ", " << j.se << ") ";
puts("");
}
puts("");
}
int Solution2::dijkstra(int s, int t, int n, int cost)
{
dis[s] = 0; vis[s] = 1;
for(int i = 0; i < n * n; ++i){
int mini = inf, u = 0;
for(int j = 0; j < n * n; ++j)
if(!vis[j] && dis[j] < mini) mini = dis[j], u = j;
vis[u] = 1;
for(auto i: g[u]){
if(!vis[i.fi] && dis[u] + i.se < dis[i.fi]) {
dis[i.fi] = min(dis[i.fi], dis[u] + i.se); // handle multiple edges
pre[i.fi] = u; // record the predecessor
}
}
}
return cost + dis[t];
}
int Solution2::getShortestPath(int n, vector<vector<int>>& cost)
{
graphModeling(n, cost);
int ans = dijkstra(0, n * n - 1, n, cost[0][0]);
return ans;
}
void Solution2::printShortestPath(int s, int t)
{
stack<int> sta;
sta.push(t);
while(1) {
int q = sta.top();
sta.push(pre[q]);
if(pre[q] == 0) break;
}
while(!sta.empty()) {
cout << mp[sta.top()].fi << ' ' << mp[sta.top()].se << endl;
sta.pop();
}
}
int main()
{
int n;
vector<vector<int>> cost(10, vector<int>(10, 0));
cin >> n;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
cin >> cost[i][j];
//Solution1 s1;
//cout << s1.exe(n, cost) << endl;
Solution2 s2;
cout << s2.getShortestPath(n, cost) << endl;
s2.printShortestPath(0, n * n - 1);
return 0;
}
/*
5
1 999 6 10 11
2 999 7 999 12
3 999 8 999 13
5 999 7 999 14
4 5 9 999 10
*/