<—点个赞吧QwQ

宣传一下算法提高课整理

给定一张由 $T$ 条边构成的无向图，点的编号为 $1 \\sim 1000$ 之间的整数。

求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边（可以重复经过）的最短路。

注意: 数据保证一定有解。

输入格式

第 $1$ 行：包含四个整数 $N，T，S，E$。

第 $2..T+1$ 行：每行包含三个整数，描述一条边的边长以及构成边的两个点的编号。

输出格式

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

数据范围

$2 \\le T \\le 100$,
$2 \\le N \\le 10^6$

输入样例：

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

输出样例：

10

思路

这里需要知道一点：一个第$a$短路的邻接矩阵$g_a$和一个第$b$短路的邻接矩阵$g_b$分别作为$\text{Floyd}$第一个边和第二个边时跑出来的最短路的邻接矩阵就是第$a+b$短路。
知道这个后就可以用类似快速幂思想，把第$k$短路按二进制拆分，然后这一位是$1$的就要把答案$\text{Floyd}$上基础邻接矩阵的几次方，同时可以类似预处理自己自乘后得到的基础邻接矩阵的$^2$,基础邻接矩阵的$^4$,基础邻接矩阵的$^8$$\cdots$

代码

#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 210;
int k,n,m,s,e;
int g[N][N];
int tmp[N][N];
int ans[N][N];
unordered_map <int,int> mp;
int get (int x) {
    if (!mp.count (x)) mp[x] = ++n;
    return mp[x];
}
void floyd (int a[][N],int b[][N],int c[][N]) {
    memset (tmp,0x3f,sizeof (tmp));
    for (int k = 1;k <= n;k++) {
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= n;j++) tmp[i][j] = min (tmp[i][j],b[i][k] + c[k][j]);
        }
    }
    memcpy (a,tmp,sizeof (tmp));
}
void power () {
    memset (ans,0x3f,sizeof (ans));
    for (int i = 1;i <= n;i++) ans[i][i] = 0;
    while (k) {
        if (k & 1) floyd (ans,ans,g);
        floyd (g,g,g);
        k >>= 1;
    }
}
int main () {
    cin >> k >> m >> s >> e;
    s = get (s),e = get (e);
    memset (g,0x3f,sizeof (g));
    while (m--) {
        int a,b,c;
        cin >> c >> a >> b;
        a = get (a),b = get (b);
        g[a][b] = g[b][a] = min (g[a][b],c);
    }
    power ();
    cout << ans[s][e] << endl;
    return 0;
}