题目大意：
一张 个点 条有向边的图上，有 个配送需求，需求的描述形式为 ，即需要从点 送到 ， 在时刻 之后（包括 ）可以在 领取货物，需要在时刻 之前（包括 ）送达 ，每个任务只需完成一次。
图上的每一条边均有边权，权值代表通过这条边消耗的时间。在时刻 有一个工作人员在点 上，求他最多能完成多少个配送任务。
在整个过程中，可以认为领货跟交货都是不消耗时间的，时间只花费在路程上。当然在一个点逗留也是允许的。
具体思路：
首先对全图跑一个floyed，求一下各点之间的最短路。 然后分析每一个运送路线，三进制枚举,0表示当前的货物是没有取，1表示当前的货物是在路上的，2表示已经送达。
dp[i][j]表示当前在i点所有路线的送货状态为j时的最小花费。
AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define inf 0x3f3f3f3f 5 #define LL_inf (1ll << 60) 6 const int maxn = 20 + 5; 7 const int mod = 1e9 + 7; 8 int n, m, q; 9 int dis[maxn][maxn]; 10 struct node { 11 int s, t, l, r; 12 } sto[15]; 13 void floyed() { 14 for (int i = 1; i <= n; i++) { 15 for (int j = 1; j <= n; j++) { 16 for (int k = 1; k <= n; k++) { 17 dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]); 18 } 19 } 20 } 21 } 22 int third[maxn]; 23 int dp[maxn][60005]; 24 void solve(int maxstate) { 25 memset(dp, inf, sizeof(dp)); 26 dp[1][0] = 0; 27 for (int i = 0; i <= maxstate; i++) { 28 for (int j = 1; j <= n; j++) { 29 for (int k = 1; k <= q; k++) { 30 int tmp = i % third[k + 1] / third[k]; 31 if (tmp == 0 && dp[j][i] + dis[j][sto[k].s] <= sto[k].r) { 32 dp[sto[k].s][i + third[k]] = 33 min(dp[sto[k].s][i + third[k]], max(sto[k].l, dp[j][i] + dis[j][sto[k].s]));// 注意这里应该取最大值，有可能到了还没到规定的取货时间 34 } 35 if (tmp == 1 && dp[j][i] + dis[j][sto[k].t] <= sto[k].r) { 36 dp[sto[k].t][i + third[k]] = min(dp[sto[k].t][i + third[k]], dp[j][i] + dis[j][sto[k].t]); 37 } 38 } 39 } 40 } 41 } 42 int main() { 43 scanf("%d %d %d", &n, &m, &q); 44 for (int i = 1; i <= n; i++) { 45 for (int j = 1; j <= n; j++) { 46 if (i == j) 47 dis[i][j] = 0; 48 else 49 dis[i][j] = inf; 50 } 51 } 52 int st, ed, val; 53 while (m--) { 54 scanf("%d %d %d", &st, &ed, &val); 55 dis[st][ed] = min(dis[st][ed], val); 56 } 57 for (int i = 1; i <= q; i++) { 58 scanf("%d %d %d %d", &sto[i].s, &sto[i].t, &sto[i].l, &sto[i].r); 59 } 60 floyed(); 61 third[1] = 1; 62 for (int i = 2; i <= q + 1; i++) { 63 third[i] = third[i - 1] * 3; 64 } 65 solve(third[q + 1] - 1); 66 int ans = 0; 67 for (int i = 1; i <= n; i++) { 68 for (int j = 0; j <= third[q + 1] - 1; j++) { 69 if (dp[i][j] >= inf) 70 continue; 71 int tmp = 0; 72 for (int k = 1; k <= q; k++) { 73 tmp += ((j % third[k + 1] / third[k]) == 2 ? 1 : 0); 74 } 75 ans = max(ans, tmp); 76 } 77 } 78 printf("%d ", ans); 79 return 0; 80 }