由于我太菜了，不会矩阵乘法，所以给同样不会矩阵乘法同学的福利

首先发现这题点很多边很少，实际上有用的点 $<= 2 * T$（因为每条边会触及两个点嘛）

所以我们可以把点的范围缩到 $2 * T$来，然后…

算法1 Bellman - Ford $O(NT)$

什么，限制边数？那不就是可爱的 $BellmanFord$吗？

看看复杂度，嗯嗯 $10 ^ 8$ 海星，常数超小的我肯定不用吸氧的

#pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 205, M = 105;
struct Edge{
    int u, v, w;
}e[M];
int m, n, s, t, adj[N], dis[N], bDis[N], tot;
void inline read(int &x) {
    x = 0;
    char s = getchar();
    while(s > '9' || s < '0') s = getchar();
    while(s <= '9' && s >= '0') x = x * 10 + s - '0', s = getchar();
}
int inline get(int &x) {
    return lower_bound(adj + 1, adj + 1 + tot, x) - adj;
}

int inline bellmanFord(){
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    for(register int i = 1; i <= n; i++){
        memcpy(bDis, dis, sizeof dis);
        memset(dis, 0x3f, sizeof dis);
        for(register int j = 1; j <= m; j++){
            dis[e[j].v] = min(dis[e[j].v], bDis[e[j].u] + e[j].w);
            dis[e[j].u] = min(dis[e[j].u], bDis[e[j].v] + e[j].w);
        }
    }
    return dis[t];
}



int main(){
    read(n); read(m); read(s); read(t);
    for (register int i = 1; i <= m; i++) {
        read(e[i].w); read(e[i].u); read(e[i].v);
        adj[++tot] = e[i].u;
        adj[++tot] = e[i].v;
    }
    sort(adj + 1, adj + 1 + tot);
    tot = unique(adj + 1, adj + 1 + tot) - adj - 1;
    for (register int i = 1; i <= m; i++) {
        e[i].u = get(e[i].u), e[i].v = get(e[i].v);
    }
    s = get(s), t = get(t);
    printf("%d\n", bellmanFord());
    return 0;
}

真香

算法2 倍增 + Floyd $O(T ^ 3 * log_2N)$

据说这题正解要用矩阵乘法，可我不会，咋办呢？

不如用倍增的思想，把$N$拆成二进制下的多个$1$，我们把每个$‘1’$最短路搞出来，然后拼出来最终的最短路，先预处理：

$d[i][j][l]$ 表示从 $i$ 到 $j$ 恰好经过 $2 ^ l$ 条边的最短路。

初始化 $d[i][j][0] = w[i][j]$，剩下为正无穷（注意是恰好 $N$ 条边，所以 $d[i][i][0]$ 也是非法状态）

转移也很好想：

$d[i][j][l] = min(d[i][k][l - 1] + d[k][j][l - 1])$，对于一个状态 $d[i][j][l]$，枚举中间点 $k$ 即可，所以预处理复杂度 $O(T ^ 3 * log_2N)$

接下来用二进制拼起来就行辣~，设 $g[i]$ 为这前几部走完后，从 $s$ 到 $i$ 的最短路， $f[i]$ 为当前到 $i$ 的最短路，与保卫王国的拼凑法思想差不多，即：

$f[i] = min(g[j] + d[j][i][c])$ 若 $N$ 的二进制第 $c$ 位为 $1$。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 205, M = 105;
struct Edge{
    int u, v, w;
}e[M];
int m, n, s, t, adj[N], tot, d[N][N][20], f[N], g[N];
int L;

int inline get(int x) {
    return lower_bound(adj + 1, adj + 1 + tot, x) - adj;
}
int main(){
    memset(d, 0x3f, sizeof d);
    scanf("%d%d%d%d", &n, &m, &s, &t);
    L = log2(n);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &e[i].w, &e[i].u, &e[i].v);
        adj[++tot] = e[i].u;
        adj[++tot] = e[i].v;
    }
    sort(adj + 1, adj + 1 + tot);
    tot = unique(adj + 1, adj + 1 + tot) - adj - 1;
    for (int i = 1; i <= m; i++) {
        int u = get(e[i].u), v = get(e[i].v), w = e[i].w;
        d[u][v][0] = d[v][u][0] = min(d[u][v][0], w);
    }
    s = get(s), t = get(t);

    for (int c = 1; c <= L; c++) {
        for (int i = 1; i <= tot; i++) {
            for (int j = 1; j <= tot; j++) {
                for (int k = 1; k <= tot; k++) {
                    d[i][j][c] = min(d[i][j][c], d[i][k][c - 1] + d[k][j][c - 1]);
                }
            }
        }
    }

    memset(g, 0x3f, sizeof g);
    g[s] = 0;
    for (int c = 0; c <= L; c++) {
        if(n >> c & 1) {
            memset(f, 0x3f, sizeof f);
            for (int i = 1; i <= tot; i++) 
                for (int j = 1; j <= tot; j++)
                    f[i] = min(f[i], g[j] + d[j][i][c]);
            memcpy(g, f, sizeof g);
        }
    }
    printf("%d\n", f[t]);
    return 0;
}