这是俺第一次正式接触图论了吧,储存边权啥的emmmm，还是个写bug机器啊
p.s.感谢leetcode 打卡
来
这个题其实一开始是想dfs，bfs那种搜索
但是太慢了（倒是官方题解那里用了二分，然而二分的细节处理1551）
所以用了并查集（还是照别人的题解描摹的）
思路写代码里了呜呜呜
#include<algorithm>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
/*
* 排序+加边
* 基本思路就是，将相邻两个边的权值从小到大排起来(处理相邻俩变得权值的时候最好自己定义一个结构体）
* 每加一条边就看看能不能把初始位置和结束位置联通
* 所以联通的过程其实是并查集的过程(merge)(find)
* 联通，则为ans
*/
vector<int> fa;
void start(int x) {
for (int i = 0; i < x; ++i) {
fa.push_back(i);
}
}
//int find(int x){
// if(fa[x]==x)
// return x;
// else
// return find(x);
//
//}
int find(int x){
int root = x, z;
while(root!=fa[root])
root=fa[root];
while(fa[x]!=root){
z = fa[x];
fa[x] = root;
x = z;
}
return root;
}
void merge(int x,int y) {
int ax = find(x);
int ay = find(y);
if (ax != ay) {
fa[max(ax, ay)] = min(ax, ay);
}
}
class Point{
public:
int u,v,cost;//前一个的值，后一个值，两个的差值（图需要保存位置值）
public:
Point(int u1,int v1,int cost1) {//一开始构造函数忘记写public了
u = u1;
v = v1;
cost = cost1;
}
bool operator < (const Point p) const {
return cost < p.cost;
}
};
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int n=heights.size();
int m=heights[0].size();
start(m*n);
vector<Point> points;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i > 0) {
cout << (i - 1) * m + j << " " << i * m + j << " " << abs(heights[i - 1][j] - heights[i][j])
<< endl;
points.emplace_back((i - 1) * m + j, i * m + j, abs(heights[i - 1][j] - heights[i][j]));
}
if (j > 0) {
cout << i * m + j - 1 << " " << i * m + j << " " << abs(heights[i][j - 1] - heights[i][j]) << endl;
points.emplace_back(i * m + j - 1, i * m + j, abs(heights[i][j - 1] - heights[i][j]));
}
}
}
sort(points.begin(),points.end());
int s=0;
int e=m*n-1;//fa从0 开始
for (auto& point : points){
merge(point.u,point.v);
if(find(s)==find(e))
return point.cost;
}
return 0;
}
};
int main(){
vector<vector<int>> heights={{4,3,4,10,5,5,9,2},{10,8,2,10,9,7,5,6},{5,8,10,10,10,7,4,2},{5,1,3,1,1,3,1,9},{6,4,10,6,10,9,4,6}};
Solution s;
cout<<s.minimumEffortPath(heights);
}