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
|
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
{
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("%dn", ans);
}
|
近期评论