题目描述：

描述

林克正在一个神奇的地方冒险。

这里有一张无向图，由 T 条边组成，图里点的编号在 1 到 1000 之间。

林克要从起点 S 走到终点 E，而且要恰好经过 N 条边（这些边是可以重复走的）。

现在要找出这样走的最短的路有多长。

要注意哦，数据保证一定能找到答案。

输入

第一行有四个整数 N，T，S，E 。

第二行到第 T + 1 行，每行都有三个整数，分别是一条边的长度，还有构成这条边的两个点的编号。

输出

输出一个整数，表示最短的路有多长。

数据范围2≤T≤1002≤N≤10^6

思路

AcWing 345

离散数学图解

代码实现

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map> // 用于存储顶点编号的映射

using namespace std;

const int N = 210; // 假设图中最多有210个顶点

int k, n, m, S, E; // k为最多步数，n为顶点数，m为边数，S为起点，E为终点
int g[N][N]; // 图的邻接矩阵表示，g[i][j]表示顶点i到顶点j的边的权值（如果不存在边则为无穷大）
int res[N][N]; // 结果矩阵，用于存储从每个顶点到其他顶点的最短路径长度（最多k步）

// 计算路径长度
void mul(int c[][N], int a[][N], int b[][N])
{//类Floyd算法
    static int temp[N][N]; // 临时矩阵，用于存储加法结果
    memset(temp, 0x3f, sizeof temp);
    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], a[i][k] + b[k][j]); // 更新最短路径长度
    memcpy(c, temp, sizeof temp); // 将结果复制到c矩阵
}

// 快速幂算法，用于计算g^k（即最多k步的最短路径矩阵）
void qmi()
{
    memset(res, 0x3f, sizeof res); // 初始化结果矩阵为无穷大
    for (int i = 1; i <= n; i++) res[i][i] = 0; // 对角线元素设为0，表示从顶点到自身的路径长度为0

    while (k)
    {
        if (k & 1) mul(res, res, g); // 如果k是奇数，则将g乘到res上
        mul(g, g, g); // 将g自乘，相当于g^2
        k >>= 1; // k右移一位，相当于k除以2
    }
}

int main()
{
    cin >> k >> m >> S >> E; // 输入k, m, S, E

    memset(g, 0x3f, sizeof g); // 初始化邻接矩阵为无穷大
    //这里我们来解释一下为什么不去初始化g[i][i]=0呢？
    //我们都知道在类Floyd算法中有严格的边数限制，如果出现了i->j->i的情况其实在i->i中我们是有2条边的
    //要是我们初始化g[i][i]=0,那样就没边了，影响了类Floyd算法的边数限制！
    map<int, int> ids; //虽然点数较多，但由于边数少，所以我们实际用到的点数也很少，可以使用map来离散化来赋予它们唯一的编号
    if (!ids.count(S)) ids[S] = ++n;
    if (!ids.count(E)) ids[E] = ++n;
    S = ids[S], E = ids[E];


    while (m--)
    {
        int a, b, c;
        cin >> c >> a >> b;
        if (!ids.count(a)) ids[a] = ++n;
        if (!ids.count(b)) ids[b] = ++n;
        a = ids[a], b = ids[b];

        // 更新邻接矩阵，如果当前边的权值更小，则更新
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    qmi(); // 调用快速幂算法计算最短路径

    cout << res[S][E] << endl; // 输出从S到E的最短路径长度（最多k步）

    return 0;
}