Untitled

 avatar
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