C++ 代码
//矩阵乘法,以次方的形式优化时间
#include<bits/stdc++.h>
using namespace std;
map<int, int> id;
//由于给出的点的代号并不按照顺序,可能会需要很大的空间,那么就将这些代号重新编号,而且是依次编号,这就叫做离散化
int n, t, s, e;
const int N = 1010;
int g[N][N], res[N][N];
//res为答案数组,g开始为只经过一条边的数组,而不是i与j之间的距离,res[i][j]与g[i][j]为在经过“若干”条边之后i到j之间的距离,不过res初始为经过0条边,g初始为经过一条边
int cnt = 0;
//cnt为依次的编号,到最后不在编号时,cnt就可以代表总共几个节点
void floyd(int a[][N], int b[][N], int c[][N]) {
//这里需要注意的是由于数组时按址调用,所以对于floyd(res,res,g)这个函数,a与b是相同的一个东西,只是看起来形式不一样罢了,对于a的修改,b也会进行修改,这是不正确的,会导致往后的程序(对数组的更新)发生错误,所以我们才要使用临时数组temp记录中间结果。同样的对于floyd(g,g,g)也是如此
static int temp[N][N];
//此处static没有太大用,因为在下一个语句处都要对temp进行赋值。但是也是有一些作用的,由于static在这里是静态局部变量,不在栈上分配,而是在程序的全局数据区分配,并不会在函数执行结束后自动销毁,下一次调用函数时就不用再次创建空间了,有助于提高速度,尤其是创造的空间很大时
memset(temp, 0x3f, sizeof temp);
//要初始化为“无穷大”,才能起到更新数组的作用
for (int k = 1;k <= cnt;k++) {
//先进行中间节点的枚举,这是Floyd的特点
for (int i = 1;i <= cnt;i++) {
for (int j = 1;j <= cnt;j++) {
temp[i][j] = min(temp[i][j], b[i][k] + c[k][j]);
}
}
}
memcpy(a, temp, sizeof(temp));
//将temp的值赋给a,之所以不直接用a进行计算,是因为可能会导致重复更新,这样的话可能会破坏我们原本对边数的限制
}
void qmi() {
memset(res, 0x3f, sizeof(res));
for (int i = 1;i <= cnt;i++) res[i][i] = 0;
//初始化res,注意此处res[i][i]要初始化为0,与g的初始化不同,本质上是res与g的定义不同
while (n) {
if (n & 1) {
floyd(res, res, g);
}
//如果这个位置是1,那么要更新答案数组
floyd(g, g, g);
//不管这个位置是否为1,都要更新g这个中间变量
n = n >> 1;
//n进行右移
}
}
int main()
{
cin >> n >> t >> s >> e;
memset(g, 0x3f, sizeof g);
//初始化g,不能把g[i][i]初始化为0,因为,g初始为经过一条边时两点间的距离
if (!id.count(s)) id[s] = ++cnt;
if (!id.count(e)) id[e] = ++cnt;
s = id[s]; e = id[e];
//进行编号,并且将更新起点和终点的编号
while (t--) {
int a, b, c;
cin >> c >> a >> b;
if (!id.count(a)) id[a] = ++cnt;
if (!id.count(b)) id[b] = ++cnt;
g[id[a]][id[b]] = g[id[b]][id[a]] = min(g[id[a]][id[b]], c);
//由于是无向边,所以在改变g[a][b]的同时也要改变g[b][a],并且,由于边的个数过于繁多,导致两点之间极有可能会出现平行边,那么我们就要进行比较,只取最小长度的边,符合题意要求
}
qmi();
//进行矩阵的快速幂算法
cout << res[s][e];
return 0;
}