65 lines
2.0 KiB
C++
65 lines
2.0 KiB
C++
#include <iostream>
|
|
#include <memory>
|
|
#include <vector>
|
|
|
|
class Graph {
|
|
public:
|
|
struct EdgeNode {
|
|
std::size_t end_vertex;
|
|
int weight = 1;
|
|
std::unique_ptr<EdgeNode> next = nullptr;
|
|
|
|
EdgeNode(std::size_t end_vertex, int weight, std::unique_ptr<EdgeNode>&& next = nullptr) {
|
|
this->end_vertex = end_vertex;
|
|
this->weight = weight;
|
|
this->next = std::move(next);
|
|
}
|
|
};
|
|
|
|
struct VertexNode {
|
|
int value = -1;
|
|
std::unique_ptr<EdgeNode> first_edge = nullptr;
|
|
};
|
|
|
|
std::vector<VertexNode> vertices;
|
|
|
|
explicit Graph(int vertices_size) : vertices(vertices_size) {}
|
|
|
|
void add_edge(std::size_t start_vertex, std::size_t end_vertex, int weight = 1, const bool two_dirs = false) {
|
|
// 效率上考量，向头部加边
|
|
// if (vertices[start_vertex].first_edge == nullptr) {
|
|
// vertices[start_vertex].first_edge = std::make_unique<EdgeNode>(end_vertex, weight);
|
|
// } else {
|
|
// auto head = std::move(vertices[start_vertex].first_edge);
|
|
// vertices[start_vertex].first_edge = std::make_unique<EdgeNode>(end_vertex, weight);
|
|
// vertices[start_vertex].first_edge->next = std::move(head);
|
|
// }
|
|
vertices[start_vertex].first_edge = std::make_unique<EdgeNode>(
|
|
end_vertex, weight, std::move(vertices[start_vertex].first_edge));
|
|
if (two_dirs) {
|
|
add_edge(end_vertex, start_vertex, weight, false);
|
|
}
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
std::ios::sync_with_stdio(false);
|
|
std::cin.tie(nullptr);
|
|
|
|
int n;
|
|
std::cin >> n;
|
|
Graph graph(n);
|
|
for (int i = 0; i < n - 1; i++) {
|
|
char node_c;
|
|
int edges_amount;
|
|
std::cin >> node_c >> edges_amount;
|
|
for (int _ = 0; _ < edges_amount; _++) {
|
|
int edge_weight;
|
|
std::cin >> node_c >> edge_weight;
|
|
graph.add_edge(i, node_c - 'A', edge_weight, true);
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|