记录编号	577323	评测结果	AAAAAAAAAA
题目名称	[USACO Nov07] 奶牛接力	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.056 s
提交时间	2022-10-31 17:53:20	内存使用	3.06 MiB

#include "bits/stdc++.h"

const int N = 210;
int n, t, s, e, p, cnt;
int len[N], a[N], b[N], vals[N];
int d[N][N], ans[N][N];

void mul(int a[N][N], int b[N][N]) {
    int c[N][N];
    memset(c, 0x3f, sizeof c);
    for (int k = 1; k <= p; ++ k) 
        for (int i = 1; i <= p; ++ i) 
            for (int j = 1; j <= p; ++ j) 
                if (c[i][j] > a[i][k] + b[k][j]) {
                    c[i][j] = a[i][k] + b[k][j];
                }
    memcpy(a, c, sizeof c);
}

int main() {
    freopen("relays.in", "r", stdin); 
    freopen("relays.out", "w", stdout);
    std::cin >> n >> t >> s >> e;
    vals[++ cnt] = s, vals[++ cnt] = s;
    for (int i = 1; i <= t; ++ i) {
        std::cin >> len[i] >> a[i] >> b[i]; 
        vals[++ cnt] = a[i],
        vals[++ cnt] = b[i];
    }
    std::sort(vals + 1, vals + 1 + cnt);
    p = std::unique(vals + 1, vals + 1 + cnt) - vals - 1;
    s = std::lower_bound(vals + 1, vals + 1 + p, s) - vals,
    e = std::lower_bound(vals + 1, vals + 1 + p, e) - vals;
    memset(d, 0x3f, sizeof d);
    for (int i = 1; i <= t; ++ i) {
        a[i] = std::lower_bound(vals + 1, vals + 1 + p, a[i]) - vals,
        b[i] = std::lower_bound(vals + 1, vals + 1 + p, b[i]) - vals;
        d[a[i]][b[i]] = std::min(d[a[i]][b[i]], len[i]);
        d[b[i]][a[i]] = std::min(d[b[i]][a[i]], len[i]);
    }
    memset(ans, 0x3f, sizeof ans);
    ans[s][s] = 0;
    for (; n; n /= 2, mul(d, d)) {
        if (n % 2) mul(ans, d);
    } 
    std::cout << ans[s][e] << '\n';
    return 0;
}