Untitled
unknown
plain_text
18 days ago
1.5 kB
3
Indexable
#include <bits/stdc++.h> #define Task "freebus" #define ll long long #define pii pair<int, int> #define F first #define S second #define pb push_back #define maxn 100005 using namespace std; int n, m, k, s, t, u, v, used[maxn]; struct duong { int v; ll c; }; vector<duong> ke[maxn]; ll c, d[maxn][7]; struct duong1 { ll len; int vt; int used; }; void dijkstra(int s) { fill(d + 1, d + n + 1, 1e12); fill(d[s], d[s] + k + 1, 0); priority_queue<duong1> q; q.push({0, s, 0}); while (!q.empty()) { int len = -q.top().len; int u = q.top().vt; int used = q.top().used; q.pop(); for (auto x : ke[u]) { if (d[x.v][used] > d[u][used] + x.c) { d[x.v][used] = d[u][used] + x.c; q.push({-d[x.v][used], x.v, used}); } if (used < k && d[x.v][used + 1] > d[u][used]) { d[x.v][used + 1] = d[u][used]; q.push({-d[x.v][used + 1], x.v, used + 1}); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } cin >> n >> m >> k >> s >> t; for (int i = 1; i <= m; i++) { cin >> u >> v >> c; ke[u].pb({v, c}); ke[v].pb({u, c}); } dijkstra(s); cout << d[t]; return 0; }
Editor is loading...
Leave a Comment