想象一下你是个城市基建规划者,地图上有 N 座城市,它们按以 1 到 N 的次序编号。
给你一些可连接的选项 conections,其中每个选项 conections[i] = [city1, city2, cost]
表示将城市 city1 和城市 city2 连接所要的成本。(连接是双向的,也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连)。
返回使得每对城市间都存在将它们连接在一起的连通路径(可能长度为 1 的)最小成本。 该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务,则请你返回 -1。
示例 1:
输入:N = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
输出:6
解释:
选出任意 2 条边都可以连接所有城市,我们从中选取成本最小的 2 条。
示例 2:
输入:N = 4, conections = [[1,2,3],[3,4,4]]
输出:-1
解释:
即使连通所有的边,也无法连接所有城市。
提示:
1 <= N <= 10000
1 <= conections.length <= 10000
1 <= conections[i][0], conections[i][1] <= N
0 <= conections[i][2] <= 10^5
conections[i][0] != conections[i][1]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/connecting-cities-with-minimum-cost 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class dsu
{
vector<int> f;
public:
dsu(int n)
{
f.resize(n);
for(int i = 0; i < n; ++i)
f[i] = i;
}
void merge(int a, int b)
{
int fa = find(a);
int fb = find(b);
f[fa] = fb;
}
int find(int a)
{
int origin = a;
while(a != f[a])
{
a = f[a];
}
return f[origin] = f[a];
}
};
class Solution {
public:
int minimumCost(int N, vector<vector<int>>& connections) {
dsu u(N+1);
sort(connections.begin(), connections.end(),[&](auto a, auto b){
return a[2] < b[2];//距离短的边优先
});
int edge = 0, p1, p2, dis, total = 0;
for(int i = 0; i < connections.size(); ++i)
{
p1 = connections[i][0];
p2 = connections[i][1];
dis = connections[i][2];
if(u.find(p1) != u.find(p2))//两个还未链接
{
u.merge(p1,p2);
edge++;
total += dis;
}
if(edge == N-1)
break;
}
return edge==N-1 ? total : -1;
}
};
1504 ms 158.6 MB
struct cmp
{
bool operator()(const pair<int,int>& a, const pair<int,int>& b) const
{
return a.second > b.second;//小顶堆, 距离小的优先
}
};
class Solution {
public:
int minimumCost(int N, vector<vector<int>>& connections) {
vector<bool> vis(N+1, false);
vector<vector<pair<int,int>>> edges(N+1,vector<pair<int,int>>());
for(auto& c : connections)
{
edges[c[0]].push_back({c[1],c[2]});
edges[c[1]].push_back({c[0],c[2]});
}
priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> q;
int to, distance, total = 0, edge = 0;
vis[1] = true;
for(auto& e : edges[1])
q.push(e);
while(!q.empty())
{
to = q.top().first;
distance = q.top().second;
q.pop();
if(!vis[to])
{
vis[to] = true;
total += distance;
edge++;
if(edge == N-1)
return total;
for(auto& e : edges[to])
q.push(e);
}
}
return -1;
}
};
492 ms 40.9 MB