多源最短路
1【模板】floyd
题目描述
给出一张由 n 个点 m 条边组成的无向图。
求出所有点对 (i,j) 之间的最短路径。
输入格式
第一行为两个整数 n,m，分别代表点的个数和边的条数。
接下来 m 行，每行三个整数 u,v,w，代表 u,v 之间存在一条边权为 w 的边。
输出格式
输出 n 行每行 n 个整数。
第 i 行的第 j 个整数代表从 i 到 j 的最短路径。
输入输出样例
输入 #1复制
4 4 1 2 1 2 3 1 3 4 1 4 1 1
输出 #1复制
0 1 2 1 1 0 1 2 2 1 0 1 1 2 1 0
说明/提示
对于 100% 的数据，n≤100，m≤4500，任意一条边的权值 w 是正整数且 1⩽w⩽1000。
数据中可能存在重边。
【解法】
【参考代码】
#include <iostream> #include <cstring> using namespace std; const int N = 110; // 最多110个点（适配题目数据范围） int n, m; // n=点数，m=边数 int f[N][N]; // 邻接矩阵：f[i][j] = i到j的最短距离 int main() { // 第一步：输入点数和边数 cin >> n >> m; // 第二步：初始化邻接矩阵 memset(f, 0x3f, sizeof f); // 所有距离初始化为“无穷大”（0x3f≈10亿） for (int i = 1; i <= n; i++) { f[i][i] = 0; // 自己到自己的距离为0 } // 第三步：输入m条无向边，更新邻接矩阵 for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; // 无向边：u↔v，取最小边权（防止重边） f[u][v] = f[v][u] = min(f[u][v], w); } // 第四步：Floyd核心——三层循环更新所有点对的最短距离 // k：中间点（枚举所有可能的中转点） for (int k = 1; k <= n; k++) { // i：起点 for (int i = 1; i <= n; i++) { // j：终点 for (int j = 1; j <= n; j++) { // 状态转移：i→j的最短距离 = min(原距离, i→k + k→j) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); } } } // 第五步：输出结果（n行n列） for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << f[i][j] << " "; } cout << endl; // 每行结束换行 } return 0; }2Clear And Present Danger
题目描述
农夫约翰正驾驶一条小艇在牛勒比海上航行。
海上有 N(1≤N≤100) 个岛屿，用 1 到 N 编号。约翰从 1 号小岛出发，最后到达 N 号小岛。
一张藏宝图上说，如果他的路程上经过的小岛依次出现了 A1,A2,…,AM(2≤M≤10000) 这样的序列（不一定相邻），那他最终就能找到古老的宝藏。但是，由于牛勒比海有海盗出没，约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数 Di,j(0≤Di,j≤100000) 来描述。他希望他的寻宝活动经过的航线危险指数之和最小。那么，在找到宝藏的前提下，这个最小的危险指数是多少呢？
输入格式
第一行：两个用空格隔开的正整数 N 和 M。
第二到第 M+1 行：第 i+1 行用一个整数 Ai 表示 FJ 必须经过的第 i 个岛屿。保证 A1=1,AM=N。
第 M+2 到第 N+M+1 行：第 i+M+1 行包含 N 个用空格隔开的非负整数分别表示 i 号小岛到第 1…N 号小岛的航线各自的危险指数。保证第 i 个数是 0。
输出格式
第一行：FJ 在找到宝藏的前提下经过的航线的危险指数之和的最小值。
显示翻译
题意翻译
输入输出样例
输入 #1复制
3 4 1 2 1 3 0 5 1 5 0 2 1 2 0
输出 #1复制
7
说明/提示
样例说明 #1
这组数据中有三个岛屿，藏宝图要求 FJ 按顺序经过四个岛屿：1 号岛屿、2 号岛屿、回到 1 号岛屿、最后到 3 号岛屿。每条航线的危险指数也给出了：航路(1,2),(2,3),(3,1) 和它们的反向路径的危险指数分别是 5,2,1。
FJ 可以通过依次经过 1,3,2,3,1,3 号岛屿以 7 的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求 (1,2,1,3)。我们避开了 1 号和 2 号岛屿之间的航线，因为它的危险指数太大了。
注意：测试数据中 a 到 b 的危险指数不一定等于 b 到 a 的危险指数！
Translated by @LJC00125
【解法】
【参考代码】
#include<iostream> #include<cstring> using namespace std; typedef long long LL; // 防止总距离溢出（比如多次累加大数） const int N=110; // 最多110个点（Floyd算法n³复杂度适配） const int M=1e4+10; // 最多1e4个访问点 int n, m; // n=点数，m=访问序列长度 int a[M]; // 访问序列：a[1]~a[m]是依次要走的点 int f[N][N]; // 邻接矩阵：f[i][j] = i到j的最短距离 int main() { // 第一步：输入点数n和访问序列长度m cin >> n >> m; // 第二步：输入访问序列（m个点的编号） for(int i=1; i<=m; i++) { cin >> a[i]; } // 第三步：输入初始邻接矩阵（n行n列，f[i][j]是i到j的初始距离） for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cin >> f[i][j]; } } // 第四步：Floyd算法预处理所有点对的最短路径 // k：中转点，i：起点，j：终点 for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { // 状态转移：i→j的最短距离 = min(原距离, i→k + k→j) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); } } } // 第五步：计算访问序列的总最短距离 LL ret = 0; // 用LL防止溢出 for(int i=2; i<=m; i++) { // 累加a[i-1]到a[i]的最短距离 ret += f[a[i-1]][a[i]]; } // 第六步：输出总距离 cout << ret << endl; return 0; }3灾后重建
题目背景
B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。
题目描述
给出 B 地区的村庄数 N，村庄编号从 0 到 N−1，和所有 M 条公路的长度，公路是双向的。并给出第 i 个村庄重建完成的时间 ti，你可以认为是同时开始重建并在第 ti 天重建完成，并且在当天即可通车。若 ti 为 0 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 Q 个询问 (x,y,t)，对于每个询问你要回答在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多少。如果无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村庄，或者村庄 x 或村庄 y 在第 t 天仍未重建完成，则需要输出 −1。
输入格式
第一行包含两个正整数 N,M，表示了村庄的数目与公路的数量。
第二行包含 N 个非负整数 t0,t1,⋯,tN−1，表示了每个村庄重建完成的时间，数据保证了 t0≤t1≤⋯≤tN−1。
接下来 M 行，每行 3 个非负整数 i,j,w，w 不超过 10000，表示了有一条连接村庄 i 与村庄 j 的道路，长度为 w，保证 i=j，且对于任意一对村庄只会存在一条道路。
接下来一行也就是 M+3 行包含一个正整数 Q，表示 Q 个询问。
接下来 Q 行，每行 3 个非负整数 x,y,t，询问在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多少，数据保证了 t 是不下降的。
输出格式
共 Q 行，对每一个询问 (x,y,t) 输出对应的答案，即在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多少。如果在第 t 天无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村庄，或者村庄 x 或村庄 y 在第 t 天仍未修复完成，则输出 −1。
输入输出样例
输入 #1复制
4 5 1 2 3 4 0 2 1 2 3 1 3 1 2 2 1 4 0 3 5 4 2 0 2 0 1 2 0 1 3 0 1 4
输出 #1复制
-1 -1 5 4
说明/提示
- 对于 30% 的数据，有 N≤50；
- 对于 30% 的数据，有 ti=0，其中有 20% 的数据有 ti=0 且 N>50；
- 对于 50% 的数据，有 Q≤100；
- 对于 100% 的数据，有 1≤N≤200，0≤M≤2N×(N−1)，1≤Q≤50000，所有输入数据涉及整数均不超过 105。
【解法】
【参考代码】
#include <iostream> #include <cstring> using namespace std; const int N = 210; // 村庄数量上限（210） const int INF = 0x3f3f3f3f; // 无穷大（≈10亿，大于最大可能路径和） int n, m; // n=村庄数，m=公路数 int t[N]; // t[i]：第i个村庄的重建完成时间 int f[N][N]; // 邻接矩阵：f[i][j] = i到j的最短路径长度 // Floyd核心函数：加入中转点k，更新所有i→j的最短路径 void floyd(int k) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // 状态转移：i→j的最短路径 = min(原路径, i→k + k→j) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); } } } int main() { // 第一步：输入村庄数和公路数 cin >> n >> m; // 第二步：输入每个村庄的重建完成时间（题目保证t[0]≤t[1]≤…≤t[n-1]） for (int i = 0; i < n; i++) { cin >> t[i]; } // 第三步：初始化邻接矩阵 memset(f, 0x3f, sizeof f); // 所有路径初始化为无穷大 for (int i = 0; i < n; i++) { f[i][i] = 0; // 自己到自己的路径长度为0 } // 第四步：输入公路信息（双向边） for (int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; // 双向公路，取最小长度（题目保证无重边，min可省略，但保留更通用） f[a][b] = f[b][a] = min(f[a][b], c); } // 第五步：处理查询 int Q; // 查询数量 cin >> Q; int pos = 0; // 记录当前已加入的最后一个中转点（利用t递增、查询t不下降的特性） while (Q--) { int x, y, time; // 查询：time天，x到y的最短路径 cin >> x >> y >> time; // 关键：把所有重建完成时间≤time的村庄作为中转点加入Floyd while (pos < n && t[pos] <= time) { floyd(pos); // 加入中转点pos，更新所有路径 pos++; // 下一个待加入的中转点 } // 判定输出条件： // 1. x或y未重建（t[x]/t[y] > time）；2. x到y无路径（f[x][y]=INF）→ 输出-1 if (t[x] > time || t[y] > time || f[x][y] == INF) { cout << -1 << endl; } else { cout << f[x][y] << endl; } } return 0; }4⽆向图的最⼩环问题
题目描述
给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出No solution.。
输入格式
第一行两个正整数 n,m 表示点数和边数。
接下来 m 行，每行三个正整数 u,v,d，表示节点 u,v 之间有一条长度为 d 的边。
输出格式
输出边权和最小的环的边权和。若无解，输出No solution.。
输入输出样例
输入 #1复制
5 7 1 4 1 1 3 300 3 1 10 1 2 16 2 3 100 2 5 15 5 3 20
输出 #1复制
61
说明/提示
样例解释：一种可行的方案：1−3−5−2−1。
对于 20% 的数据，n,m≤10。
对于 60% 的数据，m≤100。
对于 100% 的数据，1≤n≤100，1≤m≤5×103，1≤d≤105。
无解输出包括句号。
【解法】
【参考代码】
#include <iostream> #include <cstring> using namespace std; const int N = 110, INF = 1e8; int n, m; int e[N][N]; int f[N][N]; int main() { cin >> n >> m; // memset(e, 0x3f, sizeof e); // memset(f, 0x3f, sizeof f); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) f[i][j] = e[i][j] = INF; for(int i = 1; i <= n; i++) e[i][i] = f[i][i] = 0; for(int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; e[a][b] = e[b][a] = f[a][b] = f[b][a] = min(e[a][b], c); } int ret = INF; for(int k = 1; k <= n; k++) { // 最⼩环 for(int i = 1; i < k; i++) for(int j = i + 1; j < k; j++) ret = min(ret, f[i][j] + e[i][k] + e[k][j]); // 最短距离 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); } if(ret == INF) cout << "No solution." << endl; else cout << ret << endl; return 0; }
