[编程题] 送外卖2

时间限制：1秒

空间限制：32768K
美团外卖日订单数已经超过1200万，实时调度系统是背后的重要技术支撑，其中涉及很多复杂的算法。下面的题目是某类场景的抽象。

一张 n 个点 m 条有向边的图上，有 q 个配送需求，需求的描述形式为( s_i , t_i , l_i , r_i )，即需要从点 s_i 送到 t_i， 在时刻 l_i 之后（包括 l_i）可以在 s_i 领取货物，需要在时刻 r_i 之前（包括 r_i）送达 t_i ，每个任务只需完成一次。 图上的每一条边均有边权，权值代表外卖配送员通过这条边消耗的时间。在时刻 0 有一个配送员在 点 1 上，求他最多能完成多少个配送任务。
在整个过程中，我们忽略了取餐与最后给用户递餐的时间（实际场景中这两个时间是无法省略的），只考虑花费在路程上的时间。另外，允许在一个点逗留。
输入描述:

第一行，三个正整数 n , m , q (2 ≤ n ≤ 0, 1 ≤ m ≤ 400, 1 ≤ q ≤ 10)。
接下来 m 行，每行三个正整数 u_i , v_i , c_i (1 ≤ u_i,v_i ≤ n, 1 ≤ c_i ≤ 20000)，表示有一条从 u_i 到 v_i 耗时为 c_i 的有向边。
接下来 q 行，每行四个正整数 s_i , t_i , l_i , r_i (1 ≤ s_i,t_i ≤ n, 1 ≤ l_i ≤ r_i ≤ 10^6)，描述一个配送任务。

输出描述:

一个整数，表示最多能完成的任务数量。

输入例子1:

5 4 3
1 2 1
2 3 1
3 4 1
4 5 1
1 2 3 4
2 3 1 2
3 4 3 4

输出例子1:
2

解法：三进制状压DP。dp[i][j]表示三进制状态为i，最终走到j点的最小时间花费。那么状态对应一个位置是0表示没有取餐，是1表示取了餐没有送，2表示送到了，然后分析每一位上是0还是1进行状态转移，转移之前要预处理一下最短路，这个点比较少直接Floyd预处理一下即可。

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
//dp【i】【j】表示三进制下状态为i，最终走到了j点的最小时间花费
//状态对应一个位子上是0表示还没有取餐，1表示取餐了还没送，2表示送到了
struct node{
    int from, to, l, r;
}b[410];
int a[410][410];
int n, m, q, three[12];
int dp[60000][30], digit[60000][13];
void pre_deal(){
    three[0] = 1;
    for(int i=1; i<11; i++) three[i] = three[i-1]*3;
    for(int i=0; i<three[10]; i++){
        int tmp = i;
        for(int j=0; j<10; j++){
            digit[i][j] = tmp%3;
            tmp /= 3;
        }
    }
    for(int i=0; i<60000; i++)
        for(int j=0; j<30; j++)
            dp[i][j] = inf;
    memset(a, 0x3f, sizeof(a));
    for(int i=1; i<=n; i++) a[i][i]=0;
}
void Floyd(){
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            for(int k=1; k<=n; k++)
                a[j][k]=min(a[j][k],a[j][i]+a[i][k]);
}
int main()
{
    while(~scanf("%d %d %d", &n, &m, &q))
    {
        pre_deal();
        for(int i=1; i<=m; i++){
            int u,v,c;
            scanf("%d %d %d", &u,&v,&c);
            a[u][v] = min(a[u][v], c);
        }
        Floyd();
        for(int i=0; i<q; i++){
            scanf("%d %d %d %d", &b[i].from,&b[i].to,&b[i].l,&b[i].r);
        }
        dp[0][1] = 0;
        int state = 1;
        for(int i=1; i<=q; i++) state *= 3;
        for(int i=0; i<state; i++){
            for(int j=1; j<=n; j++){
                if(dp[i][j]<inf){
                    for(int k=0; k<q; k++){
                        if(digit[i][k] == 0){
                            int nxt = i+three[k];
                            int temp;
                            if(dp[i][j]+a[j][b[k].from]>=b[k].l) temp = dp[i][j]+a[j][b[k].from];
                            if(dp[i][j]+a[j][b[k].from]<b[k].l) temp = b[k].l;
                            dp[nxt][b[k].from] = min(dp[nxt][b[k].from], temp);
                        }
                        else if(digit[i][k] == 1){
                            int nxt = i+three[k];
                            if(dp[i][j]+a[j][b[k].to]<=b[k].r){
                                dp[nxt][b[k].to] = min(dp[nxt][b[k].to],dp[i][j]+a[j][b[k].to]);
                            }
                        }
                        else continue;
                    }
                }
            }
        }
        int ans = 0;
        for(int i=0; i<state; i++){
            for(int j=1; j<=n; j++){
                if(dp[i][j]<inf){
                    int cnt = 0;
                    for(int k=0; k<q; k++){
                        if(digit[i][k] == 2){
                            cnt++;
                        }
                    }
                    ans = max(ans, cnt);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}