12月20日星期六9:00-12:00
领接表存储和遍历
S+03L03【入门】邻接点
描述
一个有向图中有n个点（编号为1~n），e条边，请读入e条边，按照结点编号从小到大的顺序，输出每个点，及每个点的邻接点（有路径可到达的结点）有哪些（输出邻接点也按照编号从小到大的顺序）。
例如：有如下图所示的有向图
结点1的邻接点有：2 3 4
结点2的邻接点有：3 4
结点3的邻接点有：5
结点4的邻接点有：3 5
结点5没有邻接点
输入描述
第1行有2个整数，n和e，代表有n个点，e条边；（n≤1,000,000，e≤10,000）；
接下来e行，每行有2个整数x,y，代表x到y之间存在一有向条边（x,y≤n）
本题测试数据确保任意两点之间最多只有1条边、且数据合法，不存在x点到x点有边的情况。
输出描述
按照从小到大的顺序，先输出每个点的编号（如果该点没有出度，则该点不输出），再换行输出该点有出边可达的点的编号（也是按从小到大的顺序），输出格式请参考本题的样例。
用例输入 1
5 8
1 2
2 3
2 4
1 3
1 4
4 3
3 5
4 5
用例输出 1
1
2 3 4
2
3 4
3
5
4
3 5
提示
样例解释：
样例输入将形成如下图所示的图形，其中：
结点1的邻接点有：2 3 4
结点2的邻接点有：3 4
结点3的邻接点有：5
结点4的邻接点有：3 5
结点5没有邻接点，因此不输出
代码
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int pre[1100000]; // 以i为起点最后一条边在领接表a数组的下标
struct Edge {
int from, to, next; // 起点 终点 上一条边在领接表的下标
} a[11000], p[11000]; // a领接表
bool cmp(Edge a, Edge b) {
return a.from > b.from || (a.from == b.from && a.to > b.to);
}
// 添加边的信息到领接表a
void add(int u, int v) {
a[++k].from = u;
a[k].to = v;
a[k].next = pre[u];
pre[u] = k;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> p[i].from >> p[i].to;
}
sort(p + 1, p + 1 + m, cmp);
for (int i = 1; i <= m; i++) {
add(p[i].from, p[i].to);
}
// 输出和i相连的点
for (int i = 1; i <= n; i++) {
if (pre[i] == 0) {
continue;
}
cout << i << endl;
// j 以i为起点的链表 各个结点的在领接表的下标
for (int j = pre[i]; j != 0; j = a[j].next) {
cout << a[j].to << " ";
}
cout << endl;
}
return 0;
}
S+03Z01【入门】城市之间的最短路
描述
小丁同学准备去A国旅游，他买了一张A国的地图，地图标出了A国著名的n个旅游热门城市，并标注了这n个城市之间有m条路线相连以及每条路线的长度。
请你编程帮助小丁求出其中两个城市之间的最短距离。
输入描述
输入第一行为两个正整数n（n<=10）和m（m<=n*(n-1)/2），n表示城市个数，m表示线段个数。
接下来m行，每行输入三个整数a，b和l，表示a市与b市之间存在一条线段，线段长度为l。（a与b不同，且本题的数据中两个城市之间最多只有一条路）
每组最后一行输入两个整数x和y，表示问题：x市与y市之间的最短距离是多少。（x与y不同）
城市标号为1~n，l<=20。
输出描述
输出x市与y市之间的最短距离，如果x市与y市之间非连通，则输出“No path”。
用例输入 1
4 4
1 2 4
1 3 1
1 4 1
2 3 1
2 4
用例输出 1
3
代码
#include <bits/stdc++.h>
using namespace std;
int n, m, s, t, k;
int pre[11]; // 以i为起点,最后一条边在领接表的下标
struct Edge {
int from, to, next, len; // 起点 终点 以from为起点,上一条边在领接表的下标
} a[100]; // 无向图边数应该*2
void add(int u, int v, int len) {
a[++k].from = u;
a[k].to = v;
a[k].len = len;
a[k].next = pre[u];
pre[u] = k;
}
int d[11];
int f[11];
const int INF = 0x3f3f3f3f;
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, len;
cin >> u >> v >> len;
add(u, v, len);
add(v, u, len);
}
cin >> s >> t;
// 迪杰斯特拉算法找最短路
memset(d, 0x3f, sizeof(d));
d[s] = 0;
for (int i = 1; i <= n; i++) {
// 寻找未确定的点d数组最小值的下标
int mi = -1;
for (int j = 1; j <= n; j++) {
if (!f[j] && (mi == -1 || d[j] < d[mi])) {
mi = j;
}
}
if (f[mi] == true) {
continue;
}
f[mi] = true;
for (int j = pre[mi]; j != 0; j = a[j].next) {
if (d[mi] + a[j].len < d[a[j].to]) {
d[a[j].to] = d[mi] + a[j].len;
}
}
}
if (d[t] != INF) {
cout << d[t];
} else {
cout << "No path";
}
return 0;
}