一些个人理解的注释
C++ 代码
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
const int N = 210;
//恰好经过 k 条边, n离散化后的编号,共m条边
int k, n, m, S, E;
//从i到j经过一条边的最短路
int g[N][N];
//从i到j经过k条边的最短路
int res[N][N];
void mul(int a[][N], int b[][N], int c[][N]){
//因为a和b、c数组可能是同一数组,这里开一个临时数组
static int temp[N][N];
memset(temp, 0x3f, sizeof temp);
//这里k与Floyd算法中的k意义不同,表示从i到j恰好经过k条边的最短路
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
temp[i][j] = min(temp[i][j], b[i][k] + c[k][j]);
//注意传进来的a是一个二维数组指针,与这里的temp不一样,这里sizeof要用sizeof temp
memcpy(a, temp, sizeof temp);
}
void qmi(){
memset(res, 0x3f, sizeof res);
//初始化从i到j经过0条边的最短路
for (int i = 1; i <= n; i ++ ) res[i][i] = 0;
while (k){
if (k & 1) mul(res, res, g);
k >>= 1;
mul(g, g, g);
}
}
int main(){
cin >> k >> m >> S >> E;
map<int, int> p;
memset(g, 0x3f, sizeof g);
if (!p.count(S)) p[S] = ++ n;
if (!p.count(E)) p[E] = ++ n;
S = p[S], E = p[E];
int a, b, c;
while (m -- ){
cin >> c >> a >> b;
//离散化
if (!p.count(a)) p[a] = ++ n;
if (!p.count(b)) p[b] = ++ n;
a = p[a], b = p[b];
g[a][b] = g[b][a] = min(g[a][b], c);
}
qmi();
cout << res[S][E] << endl;
return 0;
}