bellman_ford 开O2过 1756ms

收到墨染空大佬的启发 的确bellman_ford可以做
原理：正常情况下bellman_ford算法是求解不超过k条边的最短路
如果我们每次让它强制更新的话就会变成求解恰好经过k条边的最短路
注意：第一次迭代初始点会变成INF如果题目限制的话需要特判

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    for(int i = 0; i < k; i ++)
    {
        memcopy(band, dist, sizeof dist);
        memset(dist, 0x3f, sizeof dist);//每次把点的距离初始化成INF那么它每次都会被转移
        for(int i = 0; i < m; i ++)
        {
        //因为有无向图所以每个点都可以由另一个点更新
            dist[a] = min(dist[a], dist[b] + w);
            dist[b] = min(dist[b], dist[a] + w);
        }
    }
}

exflord + 矩阵乘法

• 定义d[k][i][j] ： 从i走到j，恰好经过k条边的最短距离，因此有d[a + b][i][j] = d[a][i][k] + d[b][k][j];
• 发现结合律，可以用矩阵乘法来做，注意一些细节，看代码。
• 时间复杂度 $O(n^3logK)$

#include <iostream>
#include <cstring>
#include <map>

using namespace std;

const int N = 210;
int g[N][N], res[N][N];
int n, m, k, s, e;

void add(int a[][N], int b[][N], int c[][N])
{
    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], b[i][k] + c[k][j]);

    memcpy(a, temp, sizeof temp);
}

void qmi()
{
    memset(res, 0x3f, sizeof res); //初始化全部为正无穷
    for(int i = 1; i <= n; i ++)res[i][i] = 0;// 当前存储的是经过0条边的最短距离，

    while(k)
    {
        if(k & 1)add(res, res, g); //每次更新res
        add(g, g, g);//把距离翻倍
        k >>= 1;
    }
}
int main()
{
    memset(g, 0x3f, sizeof g);//注意只能全部初始化成正无穷，不能加上g[i][i] = 0因为当前g里面存储的单位最小距离边长为1情况下的最短距离。
    cin >> k >> m >> s >> e;
    map<int, int> S;
    if(!S.count(s))S[s] = ++ n;
    if(!S.count(e))S[e] = ++ n;
    s = S[s], e = S[e];

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

    qmi();

    cout << res[s][e] << endl;
    return 0;
}