给你初始位置和目标位置，以及一些位置之间的快速路径，普通点之间的代价为曼哈顿距离
求初始位置到目标位置最小代价
两个算法都直接使用了sp路径序列当做点，边（代价计算）定义为前一路径第二坐标到后一路径第一坐标
1. Floyd算法
class Solution {
public:
const int inf = 0x3f3f3f3f;
int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& sp) {
sp.push_back({start[0],start[1],start[0],start[1],0});//初始点加入
sp.push_back({target[0],target[1],target[0],target[1],0});//目标点加入
int n = sp.size();
vector<vector<int>> dis(n,vector<int>(n,inf));//初始化
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dis[i][j] = sp[i][4] + sp[j][4] + abs(sp[i][2] - sp[j][0]) + abs(sp[i][3] - sp[j][1]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
if(dis[i][j] > dis[i][k] + dis[k][j] - sp[k][4])//经由k节点中转，进行更新
dis[i][j] = dis[i][k] + dis[k][j] - sp[k][4];
return dis[n-2][n-1];//返回初始点到目标点最短距离
}
};
2. Dijkstra 算法
class Solution {
private:
int getCost(int x1, int y1, int x2, int y2) {
return abs(x2 - x1) + abs(y2 - y1);
}
public:
int minimumCost(vector<int>& s, vector<int>& t, vector<vector<int>>& sr) {
sr.insert(sr.begin(), {s[0], s[1], s[0], s[1], 0});//起点插入开端
sr.push_back({t[0], t[1], t[0], t[1], 0});//终点插入末尾
const int INF = INT32_MAX;
int n = sr.size();
vector<int> dist(n, INF);//源点到各点最小代价，这里具体表示各点到第二坐标的最小代价
vector<bool> vis(n, false);//记录加入集合的位置
dist[0] = 0;//从源点出发
for (int i = 0; i < n; i++) {//贪心找当前最小代价节点
int minDist = INF;//当前最小距离
int u = -1;//记录当前最小下标
for (int j = 0; j < n; j++) {
if (!vis[j] && dist[j] < minDist) {
minDist = dist[j];//进行更新
u = j;
}
}
if (u == -1) break;//没有直接剪枝
vis[u] = true;//标记加入集合，通过借助该节点更新其他最短路径
for (int v = 0; v < n; v++) {//u作为中间节点，更新到其他节点距离
if (u == v) continue;//跳过自己
int toS = getCost(sr[u][2], sr[u][3], sr[v][0], sr[v][1]);//第二坐标到第一坐标代价
int alt = dist[u] + toS + min(sr[v][4], getCost(sr[v][0], sr[v][1], sr[v][2], sr[v][3]));
dist[v] = min(dist[v], alt);//更新
}
}
return dist[n-1];//返回到终点的最小代价
}
};