sorting the edges in nondecreasing order of weight. For example, the sample contains the following edges:
1 2 9 1 3 7 2 3 10 2 4 3 After sorting, it should look like
2 4 3 1 3 7 1 2 9 2 3 10 With C++, the easiest method is to use a vector of nested pairs:
sort(v.begin(), v.end(), [](auto & it1, auto & it2) {
return it1.first < it2.first;
});
This above is a lambda expression
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int M = 4;
vector < pair<int, pair<int, int>>>v; //given as {wi,{xi,yi}}
while (M--) {
int a, b, w;
cin >> a >> b >> w;
v.push_back({w, {a, b}});
}
cout << "before sorting: \n";
for (auto it : v) {
cout << it.first << " " << it.second.first << " " << it.second.second << "\n ";
}
sort(v.begin(), v.end(), [](auto & it1, auto & it2) {
return it1.first < it2.first;
});
cout << "\nafter Sorting\n";
for (auto it : v) {
cout << it.first << " " << it.second.first << " " << it.second.second << "\n ";
}
return 0;
}
Classes
First, we need to define a class that represents what we want to sort. In our example we will define a class Edge that contains the two endpoints of the edge and the weight.
C++
A C++ struct is the same as a class in C++, but all members are public by default.
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Edge {
int x, y, w;
};
//Alternatively, We can use
// class Edge {
// public:
// int x, y, w;
// };
int main() {
int M = 4;
vector <Edge>v; //given as {wi,{xi,yi}} we got rid of pair<int, pair<int, int>> See.
while (M--) {
int a, b, w;
cin >> a >> b >> w;
v.push_back({a, b, w});
}
cout << "before sorting: \n";
for (auto it : v) {
cout << it.x << " " << it.y << " " << it.w << "\n ";
}
sort(v.begin(), v.end(), [](auto & it1, auto & it2) {
return it1.w < it2.w;
});
cout << "\nafter Sorting\n";
for (auto it : v) {
cout << it.x << " " << it.y << " " << it.w << "\n ";
}
return 0;
}