```C++
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 505; // 节点数的最大值,根据题目要求修改
int n, t, s, e;
int num[100100], tot;
struct Matrix {
int a[MAX_N][MAX_N];
};
Matrix dis, ans;
Matrix operator * (const Matrix& x, const Matrix& y) {
Matrix c;
memset(c.a, 0x3f, sizeof(c.a));
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
c.a[i][j] = min(c.a[i][j], x.a[i][k] + y.a[k][j]);
}
}
}
return c;
}
int main() {
cin >> n >> t >> s >> e;
for (int i = 1, u, v, w; i <= t; i++) {
cin >> u >> v >> w;
if (!num[u])
num[u] = ++tot;
if (!num[v])
num[v] = ++tot;
dis.a[num[u]][num[v]] = dis.a[num[v]][num[u]] = w;
}
n = tot; // 修正节点数为实际的节点总数
ans = dis;
for (--n; n; n >>= 1, dis = dis * dis) {
if (n & 1)
ans = ans * dis;
}
cout << ans.a[num[s]][num[e]] << endl;
return 0;
}
```
修改说明:
1.将 $const$ $int$ $MAXN$ 设置为 $505$,以适应题目要求的节点数范围(节点数不超过 $505$)。
2.将结构体 $Drind$ 改为 $Matrix$,并调整相应的代码。
3.修正节点数 $n$ 为实际的节点总数 $tot$。
4.在 $main$ 函数中,将 $n$ 减去 $1$,并通过 $n = tot$ 修正节点数为实际的节点总数。
5.最后输出结果时,使用 $ans.a[num[s]][num[e]]$ 来获取从 $S$ 到 $E$ 经过 $N$ 条边的最短路径长度。
by XLoffy @ 2023-07-24 14:09:53
@[XLoffy](/user/1015779) 谢谢啦!
by 北射天狼 @ 2023-07-24 14:25:34
P.S 该代码仍是错误的,现已添加修改。
1. 将 $dis$ 数组初始化
2. 调整输入输出。
3. 修改 $n$ 以及重定义乘号的过程。
by 北射天狼 @ 2023-07-24 14:34:27