最近有幸参加了学校的csp培训，现在已经进行到第四周了，而我第三周的题还没做完QAQ
可能对于一个新手来说确实有点上强度，我看好多人都在说第三周的题有力气
这个谐音梗真有意思
就在昨晚，本人正在愉悦地做dfs与bfs（其实是让ai做的），有一道题算是对我这个没学过什么算法的人来了一个降维打击
分享一下做这道题的内心obs：首先我题目就没咋读懂，当然可能是我语文不咋地（高考语文123），到后面问ai才知道那句带点号的话是什么意思--走过的路经只能包含s,t,以及1到k这几个城市
刚刚也说了，我当时做的时候满脑子都是dfs与bfs,就在我敲了几十分钟的bfs敲不出来后，我的大肥鱼告诉我这道题适合用一个别的算法：floyd
这谁绷得住
于是我也是直接学习上了
就以这道题为例
#include<bits/stdc++.h>
using namespace std;
long long a[405][405];
int n,m;
long long ans;
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(j == i)a[i][j] = 0;
else a[i][j] = 1e18;
}
}
for(int i = 1;i <= m;i++){
int u,v,t;
cin >> u >> v >> t;
a[u][v] = t;
}
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(a[i][k] != 1e18 && a[k][j] != 1e18)a[i][j] = min(a[i][j],a[i][k] + a[k][j]);
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(a[i][j] != 1e18)ans += a[i][j];
}
}
}
cout << ans << endl;
}
根据大肥鱼的说法，这个算法也是很暴力很简单，只需要几个for循环就可以得出答案
现在就来看看这几个for循环在干嘛
首先是初始化，这里分为i==j与i！=j：相等时赋值为0,意思是从原来的城市走到原来的城市的距离是0,不同时赋值为一个很大的值，意思是此路不通。
接着是赋值，读入两个城市之间的距离/所需时间（值得注意的是这道题是单向的），如果更严谨一点的话可以改成a[u][v] = min(a[u][v],t)防止重边
照片来源于洛谷b3647
然后就到了这个雷霆三层for循环了
最外层的k代表着可以经过从1到k号城市，可以理解为中转站，当然这1到k号城市也不是必须经过的，是可选择的，最终目的还是寻找最短路径。
接着是里面的两层循环，可以看到里面的if语句，他代表的意思是从i（起点）到k（中转）再到j（终点）都是通路，而后面的取最小值意思是，从i到j的最短路径是直达还是经过中转，也有可能i到j直达不通，但是可以经过k中转达到，这也就是为什么一开始的不通的路径要赋值成一个很大的数值
然后是最后的包含ans+=的for循环，他就是计算答案，注意这个循环需要加在k的for循环里面，因为题目要求需要计算k从1到n-1所有情况的和，否则答案就变小了
最后我还问了deepseek几个细节
首先就是k循环，因为他一开始给我的模板代码后面还提了一嘴有不需要k循环的情况，但是在我的紧紧逼问下，他又告诉我如果要用这个算法k循环是不可省略的（hhhh
接着我又问了这个算法的适用情况与不适用情况
（懒得打字了，大家自己看吧）
大概就是这样 今天就到这吧。
如果有错误欢迎指出
每日一歌
