看到这道题要用负权，一下子就想到了用 SPFA + dp 直接怒艹过去。
但是 Bellman-Ford 的复杂度是 $O(nm)$ 的，而数据范围是 $1 \le n \le 10^ 6, 2\le m \le 100$ 而且还有多组最短路。
我们可以结合 Floyd 的思想 AC 这道题
正好学线性代数学到了矩阵，就用矩阵乘法来解决这道题。
设 $f$ 为一个无向无权图的邻接矩阵。
$f^ {k-1}_ {i,j}$ 为 $i$ 到 $j$ 长度为 $k-1$ 的路径条数。
所以，$f$ 就为初始读入的图。
$f^ 2_ {i,j} = \sigma\limits_ {k=1}^ N f_ {i,k}f_ {k,j}$
上式满足的唯一条件，就是 $i$ 到 $k$ 联通且 $k$ 到 $j$ 联通。
接下来，我们将邻接矩阵自乘可得：
$f^ 3_ {i,j} = \sum\limits_ {x=1}^ N\sum\limits_ {y=1}^ N f_ {i,x}f_ {x,y}f_ {y,j}$
上式满足的唯一条件，就是 $i$ 到 $x$ 联通且 $x$ 到 $y$ 联通且 $y$ 到 $j$ 联通。
从上面两个式子可以总结出两个规律：
首先，$f^ k = f^ {k-1} f$
同时，$f^ 2$ 为两个节点之间有一个中转的节点，$f^ 3$ 为两个节点中有两个中转的节点，那么 $f^ k$ 就为两个节点中需要有 $k-1$ 个中转的节点。
由上两个式子可得：
$f^ k_ {i,j} = \sum\limits_ {x=1}^ N f^ {k-1}_ {i,x}f_ {x,j}$
回归题目，不难看出，题目就是上面证明的结论。
只需要把求和改成求最值即可...
因为矩阵乘法满足结合律，所以结论不变。
$f^ k_ {i,j} = \min\limits_ {x=1}^ N f^ {k-1}_ {i,x}f_ {x,j}$
然后这题用矩阵快速幂，再加上节点编号离散化，理论上就过了。
AC 代码：
// jaco2567 AK IOI
// #include <bits/stdc++.h>
#include <queue>
#include <stack>
#include <cmath>
#include <string>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
int res = 0, F = 1;
char k;
while (!isdigit(k = getchar())) if (k == '-') F = -1;
while (isdigit(k)) {
res = res * 10 + k - '0';
k = getchar();
}
return res * F;
}
const int NR = 105;
struct Matrix {
int dat[NR][NR];
Matrix() {
memset(dat, 0x3f, sizeof(dat));
}
inline int* operator [](const int i) { // 重载运算符
return dat[i];
}
} f;
int n, m, k, s, e;
int id[1005];
int u, v, w;
int min(int a, int b) {
return a < b ? a : b;
}
Matrix operator *(Matrix &a, Matrix &b) { // 矩乘
Matrix c;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
}
}
}
return c;
}
Matrix qsm(Matrix a, int b) {
Matrix res = a;
for (b--; b; a = a * a, b >>= 1) {
if (b & 1) res = res * a;
}
return res;
}
int main() {
cin >> k >> m >> s >> e;
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &w, &u, &v);
u = id[u] ? id[u] : id[u] = ++n;
v = id[v] ? id[v] : id[v] = ++n;
f[u][v] = min(f[u][v], w);
f[v][u] = min(f[u][v], w);
}
s = id[s]; e = id[e];
Matrix ans = qsm(f, k);
printf("%d\n", ans[s][e]);
return 0;
}
参考资料：[链接登录后可见]
