free

Posted on | In , , ,

题目链接

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
const int INF=1e9+7;
using namespace std;
#define pii pair<int, pair<int, int> >
const int N = 10000 + 2;
const int M = 50000 + 2;
int tot, K, s, t, n, m;
int head[N], d[N][11];
struct Edge
{
    int to, w, nex;
} edge[M * 2];
priority_queue<pii, vector<pii>, greater<pii> > q;
void add(int u, int v, int w)
{
    edge[++tot] = (Edge){v, w, head[u]};
    head[u] = tot;
    edge[++tot] = (Edge){u, w, head[v]};
    head[v] = tot;
}
void dij()
{
    while (!q.empty())
        q.pop();
    memset(d, INF, sizeof(d));
    q.push(make_pair(0, make_pair(s, 0)));
    d[s][0] = 0;
    while (!q.empty())
    {
        int x = q.top().second.first, k = q.top().second.second;
        q.pop();
        for (int i = head[x]; i; i = edge[i].nex)
        {
            int y = edge[i].to, l = edge[i].w;
            if (d[x][k] + l < d[y][k])
            {
                d[y][k] = d[x][k] + l;
                q.push(make_pair(d[y][k], make_pair(y, k)));
            }
            if (k + 1 <= K && d[x][k] < d[y][k + 1])
            {
                d[y][k + 1] = d[x][k];
                q.push(make_pair(d[y][k + 1], make_pair(y, k + 1)));
            }
        }
    }
}
int main()
{
    tot=0;
    scanf("%d%d%d%d%d", &n, &m, &s, &t, &K);
    while (m--)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    dij();
    int ans = INF;
    for (int i = 0; i <= K; i++)
        ans = min(d[t][i],ans);
    printf("%d\n", ans);
}
0%