【信息学做题日记】刷最短路有感，一知半解的状态最可怕！

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 1e4;

int n, m, k, s, t;
bool vis[maxn];
ll dis[maxn];
struct edge {
    ll w;
    int to;

};

bool operator< (const edge& a, const edge& b) {
    return a.w > b.w;
}

vector<edge> g[maxn];

void dijkstra () {
    priority_queue<edge> q;
    memset(dis, 0x7f, sizeof(dis));
    q.push({0ll, s});
    dis[s] = 0;
    while (!q.empty()) {
        auto u = q.top();
        q.pop();
        if (vis[u.to]) {
            continue;
        }
        vis[u.to] = true;
        for (auto v : g[u.to]) {
            if (dis[v.to] > dis[u.to] + v.w) {
                dis[v.to] = dis[u.to] + v.w;
                v.w = dis[v.to];
                q.push(v);
            }
        }
    }
}
void best_coder() {
    cin >> n >> m >> k >> s >> t;
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].push_back({w, v});
        g[v].push_back({w, u});
        for (int j = 1; j <= k; ++j) {
            g[j * n + u].push_back({w, j * n + v});
            g[j * n + v].push_back({w, j * n + u});
            g[(j - 1) * n + u].push_back({0, j * n + v});
            g[(j - 1) * n + v].push_back({0, j * n + u});
        }
    }
    dijkstra();
    ll ans = LONG_LONG_MAX;
    for (int i = 0; i <= k; ++i) {
        ans = min(ans, dis[i * n + t]);
    }
    cout << ans;
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}