邻接表无向无权图

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
vector<int> e[N];
int n, m;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		// 无向无权图
		e[x].push_back(y);
		e[y].push_back(x);
	}
	// 输出某个点连接的所有的点
	for (int i = 1; i <= n; i++) {
		cout << i << ":";
		for (auto v : e[i])
			cout << v << " ";
		cout << endl;
	}
	return 0;
}

邻接表无向有权图

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
// u 起点 v 终点 ，w 权值
// (u,v,w) 代表u到 v 有一条边，权值为 w
// pair<v, w>
// pair 替换成 node
vector<pair<int, int > > e[N];
int n, m;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		// 无向有权图
		e[x].push_back(make_pair(y, z));
		e[y].push_back({x, z}); // 如果是有向有权图，只建立一条边就行
	}
	// 输出某个点连接的所有的点
	for (int i = 1; i <= n; i++) {
		cout << i << ":";
		for (auto v : e[i])
			cout << v.first << " ";
		cout << endl;
	}
	return 0;
}

邮递员送信

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int M = 1e5 + 10;
int head[N], ver[M], edge[M], nxt[M], tot;
int dis[N], dis1[N];
bool vis[N];
int head1[N], ver1[M], edge1[M], nxt1[M], tot1;
int n, m;

void add(int x, int y, int z) {
	tot++;
	ver[tot] = y;
	edge[tot] = z;
	nxt[tot] = head[x];
	head[x] = tot;
}

void add1(int x, int y, int z) {
	tot1++;
	ver1[tot1] = y;
	edge1[tot1] = z;
	nxt1[tot1] = head1[x];
	head1[x] = tot1;
}

void dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	// 优先队列，默认是大顶堆
	// - 值，大的变小的，小的变大的，前面加 - 号
	priority_queue<pair<int, int > >q;
	q.push(make_pair(0, 1));
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		// 通过点 u 去更新我们其他点的值
		for (int i = head[u] ; i ; i = nxt[i]) {
			int v = ver[i];
			int w = edge[i];
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push(make_pair(-dis[v], v));
			}
		}
	}
}

void dijkstra1() { //反图最短路
	memset(vis, 0, sizeof(vis));
	memset(dis1, 0x3f, sizeof(dis1));
	dis1[1] = 0;
	// 优先队列，默认是大顶堆
	// - 值，大的变小的，小的变大的，前面加 - 号
	priority_queue<pair<int, int > >q;
	q.push(make_pair(0, 1));
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		// 通过点 u 去更新我们其他点的值
		for (int i = head1[u] ; i ; i = nxt1[i]) {
			int v = ver1[i];
			int w = edge1[i];
			if (dis1[v] > dis1[u] + w) {
				dis1[v] = dis1[u] + w;
				q.push(make_pair(-dis1[v], v));
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
		add1(y, x, z);   // 建立反图
	}
	dijkstra();
	dijkstra1();
	long long ans = 0;
	for (int i = 1; i <= n; i++)
		ans += dis[i] + dis1[i];
	cout << ans;
	return 0;
}

最短路计数

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 2e6 + 10;
const int mod = 1e5 + 3;
int head[N], ver[M * 2], nxt[M * 2], tot;
int cnt[N];
int dis[N];
bool vis[N];
int n, m;

void add(int x, int y) {
	tot++;
	ver[tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
}

void dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	dis[1] = 0;
	cnt[1] = 1;
	// 优先队列，默认是大顶堆
	// - 值，大的变小的，小的变大的，前面加 - 号
	priority_queue<pair<int, int > >q;
	q.push(make_pair(0, 1));
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		// 通过点 u 去更新我们其他点的值
		for (int i = head[u] ; i ; i = nxt[i]) {
			int v = ver[i];
			if (dis[v] > dis[u] + 1) {
				cnt[v] = cnt[u];
				dis[v] = dis[u] + 1;
				q.push(make_pair(-dis[v], v));
			} else if (dis[v] == dis[u] + 1) {
				cnt[v] = (cnt[v] + cnt[u]) % mod;
			}
		}
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y;
		add(x, y);
		add(y, x);   // 无向图建立两条边
	}
	dijkstra();
	for (int i = 1; i <= n; i++)
		cout << cnt[i] % mod << endl;
	return 0;
}