3430.DY引擎

Time Limits: 1000 ms Memory Limits: 262144 KB

Description

BOSS送给小唐一辆车。小唐开着这辆车从PKU出发去ZJU上课了。

众所周知,天朝公路的收费站超多的。经过观察地图,小唐发现从PKU出发到ZJU的所有路径只会有N(2<=N<=300)个不同的中转点,其中有M(max(0, N-100) <=M<=N)个点是天朝的收费站。N个中转点标号为1…N,其中1代表PKU,N代表ZJU。中转点之间总共有E(E<=50,000)条双向边连接。

每个点还有一个附加属性,用0/1标记,0代表普通中转点,1代表收费站。当然,天朝的地图上面是不会直接告诉你第i个点是普通中转点还是收费站的。地图上有P(1<=P<=3,000)个提示,用[u, v, t]表示:[u, v]区间的所有中转点中,至少有t个收费站。数据保证由所有提示得到的每个点的属性是唯一的。

车既然是BOSS送的,自然非比寻常了。车子使用了世界上最先进的DaxiaYayamao引擎,简称DY引擎。DY引擎可以让车子从U瞬间转移到V,只要U和V的距离不超过L(1<=L<=1,000,000),并且U和V之间不能有收费站(小唐良民一枚,所以要是经过收费站就会停下来交完钱再走)。

DY引擎果然是好东西,但是可惜引擎最多只能用K(0<=K<=30)次。

Input

第一行有6个整数N,M,E,P,L,K分别代表:N个中转点,M个收费站,E条边,P个提示,DY引擎的有效距离L,DY引擎的使用次数K。

接下去E行,每行有3个整数u,v,w(1<=u, v<=N; 1<=w<=1,000,000)表示:u和v之间有一条长度为w的双向边。

接下去P行,每行有3个整数u,v,t(1<=u<=v<=N; 0<=t<=u-v+1)表示: [u, v] 标号区间至少有t个收费站。

Output

输出一个整数,表示小唐从PZU开到ZJU用的最短距离(瞬间转移距离当然是按0来计算的)。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
6 2 6 2 5 1

1 2 1

2 3 2

3 6 3

1 4 1

4 5 2

5 6 3

2 5 2

4 6 2

Sample Output

1
2
3
4
5
1

【样例解释】

4、5是收费站。1->2(1)->6(1)

Data Constraint

对于30%的数据保证:

2<=N<=30,max(0, N-10) <=M<=N,0<=k<=10

对于100%的数据保证:

2<=N<=300,max(0, N-100) <=M<=N,E<=50,000,1<=P<=3,000,1<=L<=1,000,000,0<=K<=30

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
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 302
#define M 50002
#define K 32

int n, m, e, p, l, t, tot, ans = inf;
int to[(M << 1) * K], len[(M << 1) * K], nxt[(M << 1) * K], head[N * K];
int edge[M][3], f[N][N], dis[N * K], vis[N * K];

void add(int u, int v, int w) {
to[++tot] = v; len[tot] = w;
nxt[tot] = head[u]; head[u] = tot;
}

void spfa(int x, int y) {
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
queue<int> q;
dis[x] = y; q.push(x);
while (!q.empty()) {
int now = q.front(); q.pop(); vis[now] = 0;
for (int i = head[now]; i; i = nxt[i])
if (dis[to[i]] > dis[now] + len[i]) {
dis[to[i]] = dis[now] + len[i];
if (!vis[to[i]]) {
vis[to[i]] = 1; q.push(to[i]);
}
}
}
}

void floyd() {
for (int k = 1; k <= n; k++)
if (!(dis[k] - dis[k - 1]))
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && i != k && j != k)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
int main() {
scanf("%d%d%d%d%d%d", &n, &m, &e, &p, &l, &t);
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= e; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[i][0] = u; edge[i][1] = v; edge[i][2] = w;
f[u][v] = f[v][u] = min(f[u][v], w);
}
for (int i = 1; i <= p; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(v, u - 1, -w);
}
for (int i = 2; i <= n; i++)
add(i, i - 1, 0), add(i - 1, i, 1);
spfa(n, m); floyd();
memset(head, 0, sizeof head); tot = 0;
for (int i = 1; i <= e; i++)
for (int k = 0; k <= t; k++) {
add(k * n + edge[i][0], k * n + edge[i][1], edge[i][2]);
add(k * n + edge[i][1], k * n + edge[i][0], edge[i][2]);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && f[i][j] <= l)
for (int k = 0; k < t; k++)
add(k * n + i, (k + 1) * n + j, 0);
spfa(1, 0);
for (int k = 0; k <= t; k++)
ans = min(ans, dis[k * n + n]);
printf("%d\n", ans);
return 0;
}