[P8312 COCI2021-2022#4] Autobus - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路： n n n数据范围很小可以用Floyd算法。注意：最多坐 k k k个不同的公交线路，这个可以考虑用两个二维数组 n o w now now和 l a s t last last分别表示当前得到的最小值和上一次得到的最小值，这样每次跑一次都是只转移一条边，跑 k k k次，除去建边用掉一次，只需要跑 k − 1 k - 1 k−1次即可。
同时发现 k k k很大，但是最多只需要 n n n次即可，故需要取最小值 m i n ( k , n ) min(k,n) min(k,n)之后跑 k − 1 k - 1 k−1次。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 21;
int d[N][N], now[N][N], last[N][N];
int main()
{
int n,m; cin>>n>>m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
d[i][j] = (i == j ? 0 : 1e9);
}
}
for(int i = 1; i <= m; ++i) {
int u,v,w; cin>>u>>v>>w;
if(u == v) continue;
d[u][v] = min(d[u][v],w);
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) now[i][j] = d[i][j];
}
int k,q; cin>>k>>q;
int mi = min(k, n);
for(int k = 2; k <= mi; ++k) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
last[i][j] = now[i][j];
}
}
for(int kk = 1; kk <= n; ++kk) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
last[i][j] = min(last[i][j], now[i][kk] + d[kk][j]);
}
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
now[i][j] = last[i][j];
}
}
}
while(q--) {
int u,v; cin>>u>>v;
if(now[u][v] == 1e9) cout<<-1<<'\n';
else cout<<now[u][v]<<'\n';
}
}