预处理cost[i][j]表示从第i天到第j天起点到终点的最短距离
f[i]表示前i天到从起点到终点的最短距离
f[0] = -K
f[i] = min(f[i], f[j - 1] + cost[j][i] + K)
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 1001
#define min(x, y) ((x) < (y) ? (x) : (y)) int n, m, K, e, d, cnt;
int f[N], cost[N][N];
bool b[N][N], flag[N], vis[N];
int head[N], to[N], next[N], val[N], dis[N];
//f[i]表示前i天从起点到终点的最小费用
//cost[i][j]表示从第i天到, b[i][j]表示第i个码头第j天是否不能用 std::queue <int> q; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline void add(int x, int y, int z)
{
to[cnt] = y;
val[cnt] = z;
next[cnt] = head[x];
head[x] = cnt++;
} inline int spfa()
{
int i, u, v;
memset(vis, 0, sizeof(vis));
memset(dis, 127, sizeof(dis));
q.push(1);
dis[1] = 0;
while(!q.empty())
{
u = q.front();
q.pop();
vis[u] = 0;
for(i = head[u]; i ^ -1; i = next[i])
{
v = to[i];
if(flag[v]) continue;
if(dis[v] > dis[u] + val[i])
{
dis[v] = dis[u] + val[i];
if(!vis[v])
{
q.push(v);
vis[v] = 1;
}
}
}
}
return dis[m];
} int main()
{
int i, j, k, l, x, y, z;
n = read();
m = read();
K = read();
e = read();
memset(head, -1, sizeof(head));
for(i = 1; i <= e; i++)
{
x = read();
y = read();
z = read();
add(x, y, z);
add(y, x, z);
}
d = read();
for(i = 1; i <= d; i++)
{
z = read();
x = read();
y = read();
for(j = x; j <= y; j++) b[z][j] = 1;
}
for(i = 1; i <= n; i++)
for(j = i; j <= n; j++)
{
memset(flag, 0, sizeof(flag));
for(k = 1; k <= m; k++)
for(l = i; l <= j; l++)
flag[k] |= b[k][l];
cost[i][j] = spfa();
}
memset(f, 127, sizeof(f));
f[0] = -K;
for(i = 1; i <= n; i++)
for(j = 1; j <= i; j++)
if(cost[j][i] <= 1e9)
f[i] = min(f[i], f[j - 1] + cost[j][i] * (i - j + 1) + K);
printf("%d\n", f[n]);
return 0;
}