本编介绍关于多源最短路的三道经典OJ题，题目难度层层递进，请先根据OJ题所在网址位置，先试着做一做，疑难卡顿点再来看看题目解析~
OJ题来源：洛谷
OJ题名：Clear And Present Danger
OJ题归属：图论基础【多源最短路】
解题算法：Floyd 算法 + 对 dp表的结果统计
📌题目细节：
📌题目所说根据藏宝图会途径一种岛屿序列，但是不一定相邻：意思是，总顺序是这样的，但是可以加入新的点当作桥梁，达到最短路径效果~
📌结果统计：题目例子：1——2——1——3，在 dp 表里面分别统计 1——2、2——1、1——3，结果之和。
#include<iostream>
using namespace std;
const int N = 110, M = 1e4 + 10;
int n, m;
int f[N][N];
int pass_through[M];
int ret;
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> pass_through[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> f[i][j];
// floyd
for (int k = 1; k <= n; k++) // 不断加入点当作桥梁
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]);
}
for (int i = 1; i < m; i++)
{
int d1 = pass_through[i], d2 = pass_through[i + 1];
ret += f[d1][d2];
}
cout << ret << endl;
return 0;
}
OJ题来源：洛谷
OJ题名：灾后重建
OJ题归属：图论基础【多源最短路】
解题算法：Floyd 算法（加点建桥梁工作需要先判断）
📌题目细节：
📌此题的编号是从 0 ~ n – 1；
📌输出 -1 的情况：a——b，a/b 还没重建好；f[a][b] 之间没有最短路。
💡经验总结：
💡再识 Floyd 算法：不断加可以加的点，加一次点之后，就在已有点的基础上更新最短路，后面再加，再在目前已有点的基础上更新最短路……
📌此题给每个点绑定一个时间，其实就是加点顺序，以时间为依据，判断能否加点。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n, m;
int f[N][N];
int t[N]; // 判断加点的依据
int pos; // 不断加入可加的点
void floyd(int k)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
int main()
{
cin >> n >> m;
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;
for (int i = 1; i <= m; i++)
{
int u, v, w; cin >> u >> v >> w;
// 虽然不需要判断重边，但是初始化成了无穷，还是要取 min 的
f[u][v] = f[v][u] = min(f[u][v], w);
}
int q; cin >> q;
pos = 0; // 中途不用删点的，一直加可以加的点
while (q–)
{
int a, b, c; cin >> a >> b >> c;
while (pos < n && t[pos] <= c) floyd(pos++);
if (t[a] > c || t[b] > c || f[a][b] == INF) cout << -1 << endl;
else cout << f[a][b] << endl;
}
return 0;
}
OJ题来源：洛谷
OJ题名：无向图的最小环问题
OJ题归属：图论基础【多源最短路】
解题算法：Floyd 算法（利用其每阶段的阶段含义）
💡算法原理：
📌按环中结点的最大值将环分成若干类
📌求解每类环的最小环
📌最终结果取所有最小环的最小值
📌题目细节：
📌dp 表与邻接矩阵分成两个表
💡经验总结：
💡0x3f3f3f3f 是 1e9 级别的，0x3f3f3f3f * 2 < int的最大值 2^32 – 1 的，但是，0x3f3f3f3f * 3 就大于 int 的范围，溢出了，此题就用了 1e8。
💡dp 表中的 f[i][j] ，从 i 走到 j 的最短路存在，就表明 i 和 j 之间是通路，此时再将 k 结点当作桥梁，直接连接在 i、j 之间，那么此时 i、j 之间就形成了环，此题给这环的叫法是，以 k 结点为最大值的环。
#include<iostream>
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;
// 初始化
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] = e[i][j] = 1e8;
for (int i = 1; i <= n; i++) f[i][i] = e[i][i] = 0;
for (int i = 1; i <= m; i++)
{
int a, b, c; cin >> a >> b >> c;
f[a][b] = f[b][a] = e[a][b] = e[b][a] = min(f[a][b], c);
}
// floyd
int ret = INF;
for (int k = 1; k <= n; k++)
{
// 枚举以k结点为最大值的环的最小环的可能情况
// i——>j 和 j——>i 的情况是同一情况，所以只需枚举矩形表一半就够，还能保证结点不重复
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;
}
