题解 | relays 题解

考虑先离散化，那么点的个数只会有 $202$ 个最多。于是复杂度里面就可以有一个 $n^3$ .考虑构造矩阵 $d^1$ 表示经过一条边的最短路，那么就会是输入进来的边。那么 $d^k$ 表示经过 $k$ 条边的最短路，则有 $d^k[i][j] = min(d^k[i][j], d^r[i][k] + d^{k-r}[k][j])$ ;然后就可以处理出 $2^x$ 次方的所有矩阵，然后 $n^3logn$ 得到最终矩阵的答案了。这个算法叫做倍增floyd

#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define inf 0x3f3f3f3f
#define il inline

namespace io {

#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')

#define I_int ll
inline I_int read() {
    I_int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
char F[200];
inline void write(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
}
#undef I_int

}
using namespace io;

using namespace std;

#define N 210

int k,m,s,e;
int x[10*N], y[10*N], v[10*N], a[10*N], lim;

struct mat {
    int m[N][N];
    mat() { memset(m, 0x3f, sizeof(m)); }
    mat operator * (const mat x) const {
        mat c;
        for(int k = 1; k <= lim; ++k) {
            for(int i = 1; i <= lim; ++i) {
                for(int j = 1; j <= lim; ++j) {
                    c.m[i][j] = min(c.m[i][j], m[i][k] + x.m[k][j]);
                }
            }
        }
        return c;
    }
}d[30];

int vis[N*50];
int main() {
    in(k);in(m);in(s);in(e); int tot = 0;
    a[++tot] = s; a[++tot] = e;
    for(int i = 1; i <= m; ++i) {
        in(v[i]), in(x[i]), in(y[i]);
        a[++tot] = x[i]; a[++tot] = y[i];
    }
    sort(a+1,a+tot+1); 
    for(int i = 1; i <= tot; ++i) 
        if(a[i] != a[i - 1]) vis[a[i]] = ++lim;
    s = vis[s]; e = vis[e];
    for(int i = 1; i <= m; ++i) {
        x[i] = vis[x[i]]; y[i] = vis[y[i]];
        d[0].m[x[i]][y[i]] = d[0].m[y[i]][x[i]] = v[i];
    }
    for(int i = 1; (1 << i) <= k; ++i) d[i] = d[i - 1] * d[i - 1];
    mat ans;
    for(int i = 1; i <= lim; ++i) ans.m[i][i] = 0;
    for(int i = 0; (1 << i) <= k; ++i) if((k>>i)&1) ans = ans * d[i];
    outn(ans.m[s][e]);
}