首页 > 代码库 > BZOJ 1395 [Baltic2005]Trip（最短路+DP）
BZOJ 1395 [Baltic2005]Trip（最短路+DP）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1354
【题目大意】
给出一些车的班次，包括起点，终点，到达起点时间区间，
到达终点时间区间，想要T时刻到达n号点，问最坏情况下的最短等待时间
【题解】
最坏情况就是每次从b时刻才出发，c时刻到达，
那么就相当于地点从x到y，时间从a到d，代价为c-b，
我们求出符合要求的最大代价，然后用最终时间T去减即可
如果没有a和d这个限制，可以直接求最长路即可，
现在考虑如何消除a和d这个时间限制，我们将每条路拆分为两个点
a点处理答案保存，d点处理最长路的计算，
按照时间节点排序，顺序求最长路即可。
【代码】
#include <cstdio>#include <algorithm>#include <cstring> using namespace std;const int N=50010;int n,m,T,t,x,y,a,b,c,d,tot,dis[N],ans[N<<1];struct ask{int x,t,id,dis;}q[N<<2];bool cmp(ask a,ask b){return a.t==b.t?a.dis>b.dis:a.t<b.t;}int main(){ scanf("%d%d%d%d",&n,&m,&T,&t); for(int i=1;i<=m;i++){ scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d); q[++tot]=(ask){x,a,i,0}; q[++tot]=(ask){y,d,i,c-b}; }q[++tot]=(ask){n+1,t,0,-2e9}; sort(q+1,q+tot+1,cmp); memset(dis,233,sizeof(dis)); dis[1]=0; for(int i=1;i<=tot;i++){ if(q[i].x==n+1)break; if(!q[i].dis)ans[q[i].id]=dis[q[i].x]; else dis[q[i].x]=max(dis[q[i].x],ans[q[i].id]+q[i].dis); }printf("%d\n",dis[T]<0?-1:t-dis[T]); return 0;}BZOJ 1395 [Baltic2005]Trip（最短路+DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。