Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <assert.h>
- #include <vector>
- #include <utility>
- #include <queue>
- #include <unordered_map>
- struct IGraph {
- virtual ~IGraph() {}
- // Добавление ребра от from к to.
- virtual void AddEdge(int from, int to, int value) = 0;
- virtual int VerticesCount() const = 0;
- virtual void GetNextVertices(int vertex, std::vector<std::pair<int, int>> &vertices) const = 0;
- virtual void GetPrevVertices(int vertex, std::vector<std::pair<int, int>> &vertices) const = 0;
- };
- struct ListGraph : public IGraph {
- explicit ListGraph(int count);
- ListGraph(const IGraph& graph);
- virtual ~ListGraph() = default;
- // Добавление ребра от from к to.
- virtual void AddEdge(int from, int to, int value);
- virtual int VerticesCount() const;
- virtual void GetNextVertices(int vertex, std::vector<std::pair<int, int>>& vertices) const;
- virtual void GetPrevVertices(int vertex, std::vector<std::pair<int, int>>& vertices) const;
- private:
- std::vector<std::vector<std::pair<int, int>>> Matrix;
- };
- ListGraph::ListGraph(int count) {
- Matrix.resize(count);
- };
- ListGraph::ListGraph(const IGraph& graph) {
- Matrix.resize(graph.VerticesCount());
- for (int i = 0; i < Matrix.size(); i++) {
- graph.GetNextVertices(i, Matrix[i]);
- }
- };
- void ListGraph::AddEdge(int from, int to, int value) {
- assert(from >= 0 && from < Matrix.size());
- assert(to >= 0 && to < Matrix.size());
- Matrix[from].push_back({ to, value });
- };
- int ListGraph::VerticesCount() const {
- return Matrix.size();
- };
- void ListGraph::GetNextVertices(int vertex, std::vector<std::pair<int, int>>& vertices) const {
- assert(vertex >= 0 && vertex < Matrix.size());
- vertices = Matrix[vertex];
- };
- void ListGraph::GetPrevVertices(int vertex, std::vector<std::pair<int, int>>& vertices) const {
- assert(vertex >= 0 && vertex < Matrix.size());
- vertices.clear();
- for (int i = 0; i < Matrix.size(); i++) {
- for (int j = 0; j < Matrix[i].size(); j++) {
- if (Matrix[i][j].first == vertex) {
- vertices.push_back({ i, Matrix[i][j].second });
- break;
- }
- }
- }
- };
- bool compare(const std::pair<int, int> &a, const std::pair<int, int> &b) {
- return a.second < b.second;
- }
- int min_tree(IGraph &input) {
- std::vector<int> weight = std::vector<int>(input.VerticesCount(), INT_MAX);
- int ans = 0;
- weight[0] = 0;
- std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(&compare)> list(&compare);
- list.push({ 0, 0 });
- while (!list.empty()) {
- std::pair<int, int> v = list.top();
- list.pop();
- std::vector<std::pair<int, int>> transfer;
- input.GetNextVertices(v.first, transfer);
- for (std::pair<int, int> u : transfer){
- if (weight[u.first] != INT_MAX)
- ans -= weight[u.first];
- if (weight[u.first] > u.second) {
- int w = u.second;
- weight[u.first] = w;
- list.push({ u.first, w });
- }
- ans += weight[u.first];
- }
- }
- return ans;
- }
- int main() {
- int n;
- std::cin >> n;
- ListGraph input(n);
- std::cin >> n;
- int from, to, value;
- for (int i = 0; i < n; i++) {
- std::cin >> from >> to >> value;
- from -= 1;
- to -= 1;
- input.AddEdge(from, to, value);
- input.AddEdge(to, from, value);
- }
- std::cout << min_tree(input);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement