记录编号	577223	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Jan08] 架设电话线	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.089 s
提交时间	2022-10-27 10:42:56	内存使用	3.91 MiB

#include "bits/stdc++.h"

using PII = std::pair<int, int>;

const int N = 1010, P = 20010;
int n, p, k;
int f[N][N];
std::map<PII, bool> st;

int e[P], ne[P], h[P], w[P], idx;

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void spfa() {
    std::queue<PII> q;
    q.push({ 1, 0 });
    f[1][0] = 0, st[{ 1, 0 }] = true;
    while (q.size()) {
        PII t = q.front(); q.pop();
        auto [u, nk] = t;
        st[t] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (std::max(f[u][nk], w[i]) < f[v][nk]) {
                f[v][nk] = std::max(f[u][nk], w[i]);
                if (!st[{ v, nk }]) {
                    q.push({ v, nk }),
                    st[{ v, nk }] = true;
                }
            }
            if (f[u][nk] < f[v][nk + 1] && nk < k) {
                f[v][nk + 1] = f[u][nk];
                if (!st[{ v, nk + 1 }]) {
                    q.push({ v, nk + 1 }),
                    st[{ v, nk + 1 }] = true;
                }
            }
        }
    }
}

int main() {
    freopen("phoneline.in", "r", stdin); 
    freopen("phoneline.out", "w", stdout);
    memset(f, 0x3f, sizeof f);
    memset(h, -1, sizeof h);
    std::cin >> n >> p >> k;
    for (int i = 1; i <= p; ++ i) {
        int x, y, z;
        std::cin >> x >> y >> z;
        add(x, y, z), add(y, x, z);
    }
    spfa();
    if (f[n][k] >= 0x3f3f3f3f / 2) {
        std::cout << -1 << '\n';
    } else {
        std::cout << f[n][k] << '\n';
    }
    return 0;
}