题目传送门
题解
一直不知道允不允许这样的情况：取了第一的任务的货物后前往配送的时候，顺路取了第二个货物。
然后发现如果不可以这样的话，那么原题就是一个 (O(n^3+q^2)) 算法就能过的题，和数据范围远远不搭配。
所以显然是允许的。根据这个数据范围，我们很容易想到状压每一个任务目前的状态：要么是还没有被接货，要么是在运送途中，要么是运送完成，这三种情况。直接用三进制状压一下，设 (dp[S][i]) 表示达到 (S) 中的状态且最终停留在了 (i) 的最小合法时间。
转移直接枚举一下下一个去给哪一个任务取货或者配送就可以了。
最后的话，找到 (f[S][i] eq infty) 的 (S) 中 (2) 的个数最多的就行了。
代码如下：
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 20 + 3;
const int M = 400 + 7;
const int Q = 10 + 3;
const int INF = 0x3f3f3f3f;
const int NP = 59049 + 7;
int n, m, q, S;
int f[N][N], bin[N], dp[NP][N];
struct Task { int s, t, l, r; } a[N];
inline void floyd() {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j) smin(f[i][j], f[i][k] + f[k][j]);
}
inline void DP() {
bin[0] = 1;
for (int i = 1; i <= q; ++i) bin[i] = bin[i - 1] * 3;
S = bin[q] - 1;
memset(dp, 0x3f, sizeof(dp));
dp[0][1] = 0;
for (int s = 0; s <= S; ++s) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= q; ++j) {
if (s / bin[j - 1] % 3 == 0) smin(dp[s + bin[j - 1]][a[j].s], std::max(dp[s][i] + f[i][a[j].s], a[j].l));
else if (s / bin[j - 1] % 3 == 1 && dp[s][i] + f[i][a[j].t] <= a[j].r) smin(dp[s + bin[j - 1]][a[j].t], dp[s][i] + f[i][a[j].t]);
}
}
}
}
inline void work() {
floyd();
DP();
int ans = 0;
for (int s = 0; s <= S; ++s)
for (int i = 1; i <= n; ++i) if (dp[s][i] != INF) {
int cnt = 0, ss = s;
while (ss) cnt += ss % 3 == 2, ss /= 3;
smax(ans, cnt);
}
printf("%d
", ans);
}
inline void init() {
read(n), read(m), read(q);
int x, y, z;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j) f[i][j] = INF;
else f[i][j] = 0;
for (int i = 1; i <= m; ++i) read(x), read(y), read(z), smin(f[x][y], z);
for (int i = 1; i <= q; ++i) read(a[i].s), read(a[i].t), read(a[i].l), read(a[i].r);
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}