**第一题链接**

这是一道简单的Floyd的模板题，只需要套模板即可

#include <cstring>
using namespace std;
const int N = 110, M = 10010;
int f[N][N];
int a[M];
int n, m;
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> a[i];
	}
	memset(f, 0x3f, sizeof f);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int x;
			cin >> x;
			f[i][j] = x;
		}
	}
	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]);
			}		
		}	
	}
	int ant = f[1][a[1]];
	for (int i = 2; i <= m; i++)
	{
		ant += f[a[i - 1]][a[i]];
	}
	cout << ant << endl;
	return 0;
 }
# **第二题[链接**](https://www.luogu.com.cn/problem/P1119)
这道题实际上就是Floyd的实现过程，代码中的while操作实际上就是顶替了for(int i=1;i<k;i++)的操作，难度一般

``` #include <iostream>
#include <cstring>
using namespace std;
int n, m;
const int N = 210, M = 20010,INF=0x3f3f3f3f;
int f[N][N],f1[N][N];
int t1[N];
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++)
	{
		int a;
		cin >> a;
		t1[i] = a;
	}
	memset(f, 0x3f3f3f, sizeof f);
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		f[y][x] = f[x][y] = min(f[x][y], z);
	}
	int q;
	cin >> q;
	int pos = 0;
	while (q--)
	{
		int w, e, r;
		cin >> w >> e >> r;
		while (pos <= n && t1[pos] <= r) floyd(pos++);

		if (t1[w] > r || t1[e] > r || f[w][e] == INF) cout << -1 << endl;
		else cout << f[w][e] << endl;
	}
	return 0;
}
# **第三题[链接**](https://www.luogu.com.cn/problem/P6175#submit)
本题的难点也是本体的要点就是在dp的过程中我们是强行加入k的，![实际上它本身就是一个环alt](https://uploadfiles.nowcoder.com/images/20260126/428189651_1769427811383/6AD01E46684492FDC8469845076424F2)
还有一个细节就是要把e[i][i]以及f[i][i]赋值为0

``` #include <iostream>
#include <cstring>
#include <algorithm> // 包含 min 函数
using namespace std;

const int N = 110;
const int INF = 0x3f3f3f3f;

int n, m;
int e[N][N], f[N][N];

int main()
{
	cin >> n >> m;

	// 错误1修正：使用 memset 初始化
	memset(e, 0x3f, sizeof e);
	memset(f, 0x3f, sizeof f);

	for (int i = 1; i <= n; i++) e[i][i] = f[i][i] = 0;

	for (int i = 1; i <= m; i++)
	{
		int u, v, d;
		cin >> u >> v >> d;
		// 无向图边权赋值
		e[u][v] = e[v][u] = f[u][v] = f[v][u] = min(f[u][v], d);
	}

	int ret = INF;

	// Floyd 求最小环
	for (int k = 1; k <= n; k++)
	{
		// 1. 先计算经过 k 的最小环 (此时 f[i][j] 还没经过 k，只经过 1~k-1)
		for (int i = 1; i < k; i++)
		{
			// 优化：j 从 1 到 i-1，避免 i==j 且利用对称性
			for (int j = 1; j < i; j++)
			{
				// 必须使用 long long 防止 INF + INF + INF 溢出 int
				long long current_cycle = (long long)f[i][j] + e[i][k] + e[k][j];

				// 错误3修正：使用 min 更新 ret
				if (current_cycle < ret) ret = current_cycle;
			}
		}

		// 2. 正常的 Floyd 状态更新
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				// 错误2修正：使用 min 取最小值
				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;
}