一、题意理解

我们有一个有向图，$n \le 20$，$m \le 400$，$q \le 10$ 个任务。

每个任务 $(s_i, t_i, l_i, r_i)$ 表示：

• 在 $s_i$ 领取货物：时间 $\ge l_i$
• 在 $t_i$ 交付货物：时间 $\le r_i$
• 领货和交货不耗时，移动耗时（边权）

起点：时刻 $0$ 在点 $1$。

目标：选择一些任务并安排顺序，使得能完成的任务数最多。

---

二、样例分析

样例图：

1 -> 2 (1)
2 -> 3 (1)
3 -> 4 (1)
4 -> 5 (1)

任务：

1. (1,2,3,4)
2. (2,3,1,2)
3. (3,4,3,4)

解释：

• 时刻0在1
• 时刻1到2（走1->2，耗时1）
• 此时任务2可领货（$l_2=1$，当前时刻1），领货后立即去3（2->3，耗时1），时刻2到达3，交货（$r_2=2$，刚好）。
• 在3逗留到时刻3（任务3 $l_3=3$），领货后去4（3->4，耗时1），时刻4到达4，交货（$r_3=4$，刚好）。

完成任务2和3，共2个。

---

三、关键点

1. 任务数 $q$ 很小（$\le 10$），可以考虑状态压缩 DP 或枚举任务顺序。
2. 我们需要知道任意两点之间的最短路径时间（Floyd 预处理）。
3. 一个任务能否完成，取决于到达 $s_i$ 的时间 $\ge l_i$ 且到达 $t_i$ 的时间 $\le r_i$。
4. 任务顺序可以任意，但必须满足时间约束。

---

四、预处理最短路径

由于 $n \le 20$，可以用 Floyd-Warshall 算法计算所有点对之间的最短时间 $dist[u][v]$。

复杂度 $O(n^3)$ 可行。

---

五、状态设计

设 $dp[mask][u]$ 表示已经完成的任务集合为 $mask$（二进制位表示），当前在点 $u$ 的最早可能时间。

• $mask$ 大小 $2^q \le 2^{10} = 1024$
• $u$ 大小 $n \le 20$
• 总状态数约 $2^{10} \times 20 \approx 2\times 10^4$

---

六、状态转移

从 $dp[mask][u]$ 出发：

1. 尝试接新任务 $i$（不在 $mask$ 中）：

   • 从 $u$ 到 $s_i$ 需要时间 $dist[u][s_i]$
   • 到达 $s_i$ 的时间 $T_1 = dp[mask][u] + dist[u][s_i]$
   • 必须在 $T_1 \ge l_i$ 才能领货（如果 $T_1 < l_i$，可以等到 $l_i$ 再领，所以实际领货时间 $start = \max(T_1, l_i)$）
   • 从 $s_i$ 到 $t_i$ 需要 $dist[s_i][t_i]$
   • 到达 $t_i$ 的时间 $T_2 = start + dist[s_i][t_i]$
   • 必须 $T_2 \le r_i$ 才能完成该任务
   • 如果可以完成，则： $ dp[mask \mid (1<<i)][t_i] = \min( dp[mask \mid (1<<i)][t_i],\ T_2 ) $

2. 也可以不接任务，直接走到其他点 $v$（不接任务单纯移动）： $ dp[mask][v] = \min( dp[mask][v],\ dp[mask][u] + dist[u][v] ) $ 但这一步其实可以省略，因为接任务时已经隐含了移动。

---

实际上，我们只需枚举下一个要接的任务，因为单纯移动可以在接任务时体现（先移动到任务起点）。

---

七、算法步骤

1. 读入 $n,m,q$，建图。
2. Floyd 计算 $dist[u][v]$（注意初始化为无穷大，$dist[i][i]=0$）。
3. 初始化 $dp[0][1] = 0$，其余 $dp=\infty$。
4. 对 $mask = 0$ 到 $2^q-1$：
   • 对每个 $u$，如果 $dp[mask][u] \neq \infty$：
     • 对每个未完成的任务 $i$：
       • $T_1 = dp[mask][u] + dist[u][s_i]$
       • $start = \max(T_1, l_i)$
       • $T_2 = start + dist[s_i][t_i]$
       • 如果 $T_2 \le r_i$：
         • $dp[mask | (1<<i)][t_i] = \min(dp[mask | (1<<i)][t_i], T_2)$
5. 答案 = 满足 $dp[mask][u] \neq \infty$ 的 $mask$ 中二进制位 1 的个数的最大值。

---

八、复杂度

• 状态数：$2^q \times n \approx 1024 \times 20 = 20480$
• 转移：每个状态尝试 $q$ 个任务 → $O(2^q \times n \times q) \approx 2\times 10^5$，可接受。

---

九、代码实现（C++）

#include <bits/stdc++.h>
#define int long long
#define FAST ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
int n, m, q;
int dis[40][40];
vector<pair<int, int>> v[40];
//v[i] 存储了在第 i 个点发生的事件
//{time,op} 时间，事件类型（接收，领取）
int f[40][59049];
int mi[40];
/*
f[i][state]当前在 i 城市，state 表示每个订单的状态，
0 表示没有领取
1 表示在车上
2 表示已经完成
所需的最小时间

枚举接下来去哪个城市？然后更新状态

可以逗留一段时间领取更多的包裹
*/
int change(int x, int op) {
    //状态，经过了 op 的洗礼
    int F = abs(op) - 1;

    int K = x % mi[F];
    x /= mi[F];

    if (x % 3 == 0 && op > 0)
        x++;
    else if (x % 3 == 1 && op < 0)
        x++;

    x *= mi[F];
    x += K;
    return x;
}
bool cmp(pair<int, int> X, pair<int, int> Y) {
    if (X.first == Y.first)
        return X.second > Y.second;

    return X.first < Y.first;
}

signed main() {
    cin >> n >> m >> q;
    memset(dis, 0x3f, sizeof(dis));

    for (int i = 1; i <= n; i++)
        dis[i][i] = 0;

    for (int i = 1; i <= m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        dis[x][y] = min(dis[x][y], c);
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }

    //  for (int i=1;i<=n;i++){
    //      for (int j=1;j<=n;j++){
    //          cout << dis[i][j] << ' ';
    //      }
    //      cout << "\n";
    //  }
    for (int i = 1; i <= q; i++) {
        int s, t, l, r;
        cin >> s >> t >> l >> r;
        v[s].push_back({l, i});
        v[t].push_back({r, -i});
    }

    mi[0] = 1;

    for (int i = 1; i <= q; i++)
        mi[i] = mi[i - 1] * 3;

    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end(), cmp);
    }

    memset(f, 0x3f, sizeof(f));

    //f[i] 只要不是 inf 就可以贡献到答案
    for (int i = 1; i <= n; i++)
        f[i][0] = dis[1][i];

    int ans = 0;

    for (int st = 0; st < mi[q]; st++) {
        for (int cur = 1; cur <= n; cur++) {
            //必须逗留到状态改变了才能去其它城市
            int to = st;
            int MX = f[cur][st];

            for (auto j : v[cur]) {
                if (j.second > 0) {
                    to = change(to, j.second);
                    MX = max(MX, j.first);
                } else {
                    if (j.first >= f[cur][st])
                        to = change(to, j.second);
                }

                if (to != st) {
                    //改变咯！
                    for (int k = 1; k <= n; k++)
                        f[k][to] = min(f[k][to], MX + dis[cur][k]);
                }
            }

            if (f[cur][st] < 1e18) {
                int cnt = 0, C = st;

                while (C) {
                    if (C % 3 == 2)
                        ++cnt;

                    C /= 3;
                }

                ans = max(ans, cnt);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

---

十、总结

本题的关键在于：

1. 利用 $q$ 小的特点进行状态压缩 DP。
2. 预处理任意两点最短路径。
3. 状态设计为 $(mask, u)$ 表示已完成任务集合和当前位置。
4. 转移时检查时间约束：领货时间 $\ge l_i$，交货时间 $\le r_i$。