You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
75 lines
1.9 KiB
C++
75 lines
1.9 KiB
C++
#include <cstdio>
|
|
#include <cstring>
|
|
inline int min(int a, int b) { return a < b ? a : b; }
|
|
int next[410], to[410], len[410], G[21], e_idx;
|
|
int que[100001], head, tail;
|
|
bool inque[21], isbad[21], cant[21][101];
|
|
int cost[110][110], f[101];
|
|
inline void addEdge(int f, int t, int l)
|
|
{
|
|
e_idx++;
|
|
to[e_idx] = t;
|
|
len[e_idx] = l;
|
|
next[e_idx] = G[f];
|
|
G[f] = e_idx;
|
|
}
|
|
void spfa(int s)
|
|
{
|
|
memset(inque, 0, sizeof(inque));
|
|
memset(f, 0x3f, sizeof(f));
|
|
head = tail = 0;
|
|
f[s] = 0;
|
|
que[tail++] = s;
|
|
inque[s] = true;
|
|
while (head < tail)
|
|
{
|
|
int x = que[head++];
|
|
inque[x] = false;
|
|
for (int i = G[x]; i; i = next[i])
|
|
if (!isbad[to[i]])
|
|
if (f[to[i]] > f[x] + len[i])
|
|
{
|
|
f[to[i]] = f[x] + len[i];
|
|
if (!inque[to[i]]) inque[que[tail++] = to[i]] = true;
|
|
}
|
|
}
|
|
}
|
|
int main()
|
|
{
|
|
int n, m, k, e, d;
|
|
scanf("%d%d%d%d", &n, &m, &k, &e);
|
|
for (int i = 0, x, y, z; i < e; i++)
|
|
{
|
|
scanf("%d%d%d", &x, &y, &z);
|
|
addEdge(x, y, z);
|
|
addEdge(y, x, z);
|
|
}
|
|
scanf("%d", &d);
|
|
for (int i = 0, x, y, z; i < d; i++)
|
|
{
|
|
scanf("%d%d%d", &x, &y, &z);
|
|
for (int j = y; j <= z; j++)
|
|
cant[x][j] = true;
|
|
}
|
|
for (int i = 1; i <= n; i++)
|
|
for (int j = i; j <= n; j++)
|
|
{
|
|
memset(isbad, 0, sizeof(isbad));
|
|
for (int x = 2; x < m; x++)
|
|
for (int y = i; y <= j; y++)
|
|
if (cant[x][y])
|
|
{
|
|
isbad[x] = true;
|
|
break;
|
|
}
|
|
spfa(1);
|
|
cost[i][j] = f[m] * (f[m] > 0x3f3f3f3f >> 1 ? 1 : j - i + 1);
|
|
}
|
|
memset(f, 0x3f, sizeof(f));
|
|
f[0] = 0;
|
|
for (int i = 1; i <= n; i++)
|
|
for (int j = 0; j < i; j++)
|
|
f[i] = min(f[i], f[j] + cost[j + 1][i] + k);
|
|
printf("%d", f[n] - k);
|
|
return 0;
|
|
} |