每日太水
來寫個不一樣的
題目;
1584. Min cost to connect all point
用最短的路把所有點都連在一起
路徑長直接用x跟y的差距就好
叫啥曼哈頓距離的
思路:
因為只要全部連在一起
所以誰連誰都可以
用map記所有人的路徑
然後隨便一個點開始
每次都找最近的連
這樣一定可以找到最短的路
自己寫了一些幹東西
筆記
unordered map的hash value
需要弄運算子==
作為比較時的方法
priority queue 需要
弄運算子>或<
當作greater或less比較的方法
```cpp
struct point
{
int x ;
int y ;
int idx ;
bool operator<(const point& other) const
{
if (x == other.x) return y < other.y;
return x < other.x;
}
bool operator==(const point& other) const {
return x == other.x && y == other.y && idx == other.idx;
}
};
struct point_hash {
std::size_t operator() (const point &p) const {
std::size_t h1 = std::hash<int>{}(p.x);
std::size_t h2 = std::hash<int>{}(p.y);
return h1 ^ (h2 << 1);
}
};
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points)
{
unordered_map<point,vector<point> , point_hash> save;
int n = points.size();
for(int i = 0 ; i < n ; i ++)
{
point now;
now.x = points[i][0];
now.y = points[i][1];
now.idx = i;
for(int j = i+1 ; j < n ; j ++){
point next;
next.x = points[j][0];
next.y = points[j][1];
next.idx = j ;
save[now].push_back(next);
save[next].push_back(now);
}
}
point first;
first.x = points[0][0];
first.y = points[0][1];
first.idx = 0;
priority_queue<pair<int,point> , vector<pair<int,point>> , greater<pair<
int,point>> > pq;
pq.push({0,first});
vector<int> passed(n,0);
int nowpass = 0;
int all = 0;
while(!pq.empty())
{
int nowdist = pq.top().first;
point now = pq.top().second;
pq.pop();
if(passed[now.idx])continue;
passed[now.idx] = 1;
all += nowdist;
nowpass ++;
if(nowpass == n)return all;
for(point next : save[now]){
int dist = abs(next.x-now.x) + abs(next.y - now.y);
pq.push({dist,next});
}
}
return all;
}
};
```