美团codeM预赛B 送外卖2

送外卖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

解题思路：状压每个货物的(未领、已领、已到)状态，每层状态保存最早到达点 i 的时间，每一层用 dijkstra 暴力更新最早时间

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <stack> #include <cmath> #include <map> #include <bitset> #include <set> #include <vector> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; int n,m,q,u,v,c; int f[15],t[15],l[15],r[15],a[15],p[15]; int s[25],nt[405],e[405],cost[405]; int dp[60005][25]; bool vis[25]; int main() { while(~scanf("%d%d%d",&n,&m,&q)) { memset(s,-1,sizeof s); int cnt=1,x=1,ans=0; for(int i=1; i<=m; i++) { scanf("%d%d%d",&u,&v,&c); nt[cnt]=s[u],s[u]=cnt,e[cnt]=v,cost[cnt++]=c; } for(int i=1; i<=q; i++,x*=3)scanf("%d%d%d%d",&f[i],&t[i],&l[i],&r[i]),p[i]=x; memset(dp,INF,sizeof dp); dp[0][1]=0; for(int i=0; i<x; i++) { memset(vis,0,sizeof vis); for(int j=1; j<=n; j++) { u=0; for(int k=1; k<=n; k++) if(!vis[k]&&(!u||dp[i][k]<dp[i][u])) u=k; vis[u]=1; for(int k=s[u]; ~k; k=nt[k]) if(dp[i][u]+cost[k]<dp[i][e[k]]) dp[i][e[k]]=dp[i][u]+cost[k]; } for(int j=1,k=i; j<=q; j++,k/=3) a[j]=k%3; int sum=0; for(int j=1; j<=q; j++) { if(a[j]==0) { if(max(l[j],dp[i][f[j]])<dp[i+p[j]][f[j]]) dp[i+p[j]][f[j]]=max(l[j],dp[i][f[j]]); } else if(a[j]==1&&dp[i][t[j]]<=r[j]) { if(dp[i][t[j]]<dp[i+p[j]][t[j]]) dp[i+p[j]][t[j]]=dp[i][t[j]]; } else if(a[j]==2) sum++; } for(int j=1;j<=n;j++) if(dp[i][j]<INF) ans=max(ans,sum); } printf("%d\n",ans); } return 0; }