UVa 12661 Funny Car Racing

题目描述在一个城市中有nnn个路口和mmm条有向道路举办了一场有趣的赛车比赛。特别之处在于每条道路都会周期性地开放和关闭。每条道路关联两个整数(a,b)(a, b)(a,b)表示道路会开放aaa秒然后关闭bbb秒接着再开放aaa秒……如此循环从比赛开始时计时。你必须在道路开放时进入并在道路关闭前离开。你的目标是从路口sss出发尽可能早地到达路口ttt。注意即使所有相邻道路都关闭你也可以在路口等待。输入格式多组测试数据最多303030组每组第一行n,m,s,tn, m, s, tn,m,s,t(1≤n≤3001 \leq n \leq 3001≤n≤300,1≤m≤50,0001 \leq m \leq 50,0001≤m≤50,000,1≤s,t≤n1 \leq s, t \leq n1≤s,t≤n)接下来mmm行u,v,a,b,tu, v, a, b, tu,v,a,b,t(1≤u,v≤n1 \leq u, v \leq n1≤u,v≤n,1≤a,b,t≤1051 \leq a, b, t \leq 10^51≤a,b,t≤105)u,vu, vu,v道路起点和终点aaa开放时间bbb关闭时间ttt通过该道路所需时间输出格式每组数据输出最短时间秒。题目分析这是一个带时间窗口约束的最短路问题。与传统最短路径问题不同每条边有特定的开放和关闭周期我们只能在开放时间段内进入道路并且通过时间不能超过开放时长。关键约束条件周期性开放每条道路的开放-关闭周期为TabT a bTab进入限制必须在道路开放时进入通过时间限制通过时间ttt必须≤a\leq a≤a否则永远无法通过等待策略可以在路口等待道路开放核心挑战对于当前时间curTimecurTimecurTime和边(u,v,a,b,t)(u, v, a, b, t)(u,v,a,b,t)需要计算实际到达vvv的时间如果tat ata直接忽略无法通过计算在周期中的位置rcurTime mod Tr curTime \bmod TrcurTimemodT分情况讨论rar ara且t≤a−rt \leq a - rt≤a−r立即出发arrivalcurTimetarrival curTime tarrivalcurTimetrar ara但ta−rt a - rta−r等待到下一周期arrivalcurTime(T−r)tarrival curTime (T - r) tarrivalcurTime(T−r)tr≥ar \geq ar≥a当前关闭等待到下一周期开放arrivalcurTime(T−r)tarrival curTime (T - r) tarrivalcurTime(T−r)t解题思路算法选择使用Dijkstra\texttt{Dijkstra}Dijkstra算法的变种因为需要找到从sss到ttt的最短时间路径边权非负等待时间是非负的可以在松弛时处理时间窗口约束算法步骤初始化dist[i]dist[i]dist[i]表示到达路口iii的最早时间初始为无穷大dist[s]0dist[s] 0dist[s]0优先队列使用最小堆按时间排序初始将(s,0)(s, 0)(s,0)加入队列Dijkstra\texttt{Dijkstra}Dijkstra主循环取出当前时间最小的路口uuu如果utu tut提前结束遍历uuu的所有出边跳过tat ata的边计算实际到达时间考虑等待如果新时间更优更新dist[v]dist[v]dist[v]并加入队列复杂度分析时间复杂度O((nm)log⁡n)O((n m) \log n)O((nm)logn)每个节点和边最多被处理一次优先队列操作是O(log⁡n)O(\log n)O(logn)空间复杂度O(nm)O(n m)O(nm)代码实现// Funny Car Racing// UVa ID: 12661// Verdict: Accepted// Submission Date: 2025-11-05// UVa Run Time: 0.040s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includeiostream#includevector#includequeue#includeclimitsusingnamespacestd;// 边的数据结构structEdge{intv,a,b,t;// 终点、开放时间、关闭时间、通过时间};// 优先队列中的状态structState{intu,time;// 当前节点、到达该节点的时间booloperator(constStateother)const{returntimeother.time;// 最小堆时间小的优先}};intmain(){ios_base::sync_with_stdio(false);cin.tie(NULL);intn,m,s,t;intcaseNum1;// 测试用例编号// 处理多组测试数据while(cinnmst){// 构建邻接表vectorvectorEdgegraph(n1);// 读入每条道路信息for(inti0;im;i){intu,v,a,b,tt;cinuvabtt;// 只有通过时间 开放时间才可能使用这条道路if(tta){graph[u].push_back({v,a,b,tt});}}// 初始化距离数组vectorintdist(n1,INT_MAX);dist[s]0;// 优先队列Dijkstra算法priority_queueStatepq;pq.push({s,0});while(!pq.empty()){State curpq.top();pq.pop();intucur.u;intcur_timecur.time;// 如果当前时间不是最优跳过if(cur_timedist[u])continue;// 如果到达目标节点提前结束if(ut)break;// 遍历所有出边for(constEdgee:graph[u]){intve.v;intae.a;intbe.b;inttte.t;intTab;// 周期// 计算在当前周期中的位置intrcur_time%T;intarrival_time;if(ra){// 当前道路开放if(tta-r){// 可以在当前开放时段内通过arrival_timecur_timett;}else{// 需要等待到下一周期arrival_timecur_time(T-r)tt;}}else{// 当前道路关闭需要等待到下一周期开放arrival_timecur_time(T-r)tt;}// 如果找到更早的到达时间更新if(arrival_timedist[v]){dist[v]arrival_time;pq.push({v,arrival_time});}}}// 输出结果coutCase caseNum: dist[t]\n;}return0;}总结本题的关键在于将传统的最短路径算法与时间窗口约束相结合。通过仔细分析道路的开放关闭周期并在Dijkstra\texttt{Dijkstra}Dijkstra算法的松弛步骤中正确处理等待时间我们能够有效地解决这类带时间约束的路径规划问题。这种思路可以扩展到其他类似的周期性约束问题如公共交通调度、网络数据传输等场景。