请编写程序创建一个有向图。有向图中包含n个顶点,编号为0至n-1。 输入格式: 输入第一行为两个正整数n和e,分别表示图的顶点数和边数,其中n不超过20000,e不超过20000。接下来e行表示每条边的信息,每行为3个非负整数a、b、c,其中a和b表示该边的端点编号,c表示权值。各边并非按端点编号顺序排列。 输出格式: 按顶点编号递增顺序输出每个顶点引出的边,每个顶点占一行,若某顶点没有引出边,则不输出。每行表示一个顶点引出的所有边,格式为a:(a,b,w)……,表示有向边a->b的权值为w,a引出的多条边按编号b的递增序排列。用c代码实现
时间: 2024-02-18 13:05:23 浏览: 25
以下是C++的实现代码,使用邻接表存储有向图:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, e;
cin >> n >> e;
// 邻接表存储有向图
vector<vector<pair<int, int>>> graph(n);
for (int i = 0; i < e; i++) {
int a, b, w;
cin >> a >> b >> w;
graph[a].push_back(make_pair(b, w));
}
// 输出每个顶点引出的边
for (int i = 0; i < n; i++) {
if (!graph[i].empty()) {
sort(graph[i].begin(), graph[i].end());
cout << i << ":";
for (auto& p : graph[i]) {
cout << "(" << i << "," << p.first << "," << p.second << ")";
}
cout << endl;
}
}
return 0;
}
```
代码思路:
1. 读入顶点数n和边数e;
2. 创建空的邻接表graph;
3. 读入每条边的信息,将其添加到对应的起点的邻接表中;
4. 遍历每个顶点,如果有邻接点,则按编号递增排序后输出。
阅读全文