邻接表无向无权图
#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;
}
// n个点 m 条边
// 给边赋权值，范围 1-k
// 保证从 1 到 每个点的最短路是唯一的
// 1...2 3 1...2 3
// 让所有的边权都为 1
// 跑最短路，
// dis[v] > dis[u] + 1 , 新的最短路，更新
// dis[v] （之前的最短路）== dis[u] + 1 (新的最短路)
// 有两条最短路，让其中一条不是最短路就行了
// 增加 u - v 这条边的边权, 从 u 到 v 不是最短路了？？？
// 统计边权的最大值，最大值大于 k ,不能 NO
//
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int T, n, m, k;
int head[N], ver[N], nxt[N], tot, edge[N];
int f[N];
bool vis[N];
int maxx;
void add(int x, int y) {
tot++;
edge[tot] = 1; // 将所有的边权最开始都设置 1
nxt[tot] = head[x];
head[x] = tot;
ver[tot] = y;
}
void dijkstra() {
// 多组测试数据
maxx = 0;
memset(f, 0x3f, sizeof(f));
memset(vis, 0, sizeof(vis));
f[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;
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
int w = edge[i];
if (f[v] > f[u] + w) {
f[v] = f[u] + w;
q.push({-f[v], v});
} else if (f[v] == f[u] + w) { // 如果出现了两条长度一样的最短路
++edge[i]; // 把从 u 到 v 的这条边的长度增加 1
// 改变了边的权值，但是边的权值 1 - k
maxx = max(maxx, edge[i]); // 记录下来所有的边的权值的最大值
}
}
}
if (maxx > k)
cout << "No" << endl;
else {
cout << "Yes" << endl;
for (int i = 1; i <= m; i++)
cout << edge[i] << " ";
cout << endl;
}
}
int main() {
cin >> T;
while (T--) {
cin >> n >> m >> k;
tot = 0;
memset(head, 0, sizeof(head));
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
add(x, y);
}
dijkstra();
}
return 0;
}
拓扑排序
// 拓扑排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
const int M = 1e4 + 10;
int n;
int head[N], nxt[M], ver[M], tot;
int in[N]; // 入度
void add(int x, int y) {
tot++;
ver[tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void topsort() {
queue<int> q;
// 1. 所有入度为 0 的点入队
for (int i = 1; i <= n; i++) {
if (in[i] == 0)
q.push(i);
}
// 2. 依次从队列里面取点出队处理
while (!q.empty()) {
int u = q.front(); // 取到队列头部的点
q.pop();
cout << u << " "; // 输出拓扑序列
// 3. 处理和 点 u 相连的点
for (int i = head[u] ; i ; i = nxt[i]) {
int v = ver[i];
// 4. 删除 u 和 v 连接的这条边
in[v]--;
if (in[v] == 0)
q.push(v);
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int tmp;
while (cin >> tmp) {
if (tmp == 0)
break;
add(i, tmp);
in[tmp]++; // i 指向 tmp, tmp 的入度增加
}
}
topsort();
return 0;
}
