UVa 771 Flying Stars

题目描述给定若干机场以及每日循环的航班信息。每个机场有固定的时区偏移和登机 / 转机耗时。从起点机场的某个本地时刻出发需要经过一系列航班抵达终点机场。要求计算从出发时刻到抵达终点时刻的总旅行时间以天、小时、分钟表示并输出抵达终点时的本地时间以及最优路径上各航班的标识符。输入格式每个测试用例由多行组成。第一行包含起点机场标识符、终点机场标识符和出发本地时间格式hh:mm。第二行是一个整数NNN2≤N≤1002 \le N \le 1002≤N≤100表示机场总数。接下来NNN个机场的描述每个描述以标题行开始机场标识符、时区格式shh:mm或-、登机耗时格式hh:mm和一个整数MMMM≤300M \le 300M≤300表示该机场的航班数。随后MMM行每行描述一个航班航班标识符、目的地机场标识符、起飞本地时间格式hh:mm和飞行时长格式hh:mm。多个测试用例之间由空行分隔。输出格式对于每个测试用例第一行输出总旅行时间格式d:hh:mm其中ddd为完整天数不超过999。第二行输出抵达终点时的当地时间格式hh:mm。随后每行输出最优路径上的一个航班标识符顺序与乘坐顺序一致。相邻测试用例的输出之间用空行分隔。样例输入Pulkovo JFK 11:15 3 Pulkovo 03:00 01:30 2 BA347 Heathrow 12:10 04:25 Z8805 Heathrow 18:25 04:30 Heathrow 00:00 00:45 3 BA160 JFK 09:20 08:10 BA346 Pulkovo 14:45 04:20 Z8804 Pulkovo 21:30 04:25 JFK -05:00 00:45 1 BA161 Heathrow 14:25 08:05输出1:09:15 12:30 Z8805 BA160题目分析本题要求从起点机场到终点机场的最快路径其中速度由航班飞行时长决定但路径选择受限于每日循环的航班时刻表以及各机场的转机等待时间。同时机场分布在不同的时区所有时间均为当地时间因此需要统一到某个绝对时间轴上进行计算。若以到达某个机场的绝对时刻作为状态则在每个机场可以选择后续航班其中航班能否乘坐取决于当地时间的起飞时刻是否晚于当前时刻加上该机场的登机耗时即最早可登机时刻。由于航班每日循环若当天合适航班已过则需要等待到次日同一时刻。问题的难点在于时间的本地与绝对转换以及时区差的处理。航班时刻的循环性质使得等待时间需要模144014401440分钟计算。节点数最多100100100每个机场最多300300300个航班总边数3×1043 \times 10^43×104可以使用最短路径算法。解题思路时间模型设起点机场为SSS其时区偏移为ΔS\Delta_SΔS​分钟。将起点出发的本地时间t0t_0t0​分钟范围0∼14390 \sim 14390∼1439作为绝对时间000的基准。对于任意机场AAA其在绝对时间TTT分钟对应的当地时间为localA(T)(t0T(ΔA−ΔS)) mod 1440 \textit{local}_A(T) (t_0 T (\Delta_A - \Delta_S)) \bmod 1440localA​(T)(t0​T(ΔA​−ΔS​))mod1440其中结果规范到[0,1439][0, 1439][0,1439]。反之若已知某机场的当地时间为LLL则对应的绝对时间TTT需满足T≡L−t0−(ΔA−ΔS)(mod1440)T \equiv L - t_0 - (\Delta_A - \Delta_S) \pmod{1440}T≡L−t0​−(ΔA​−ΔS​)(mod1440)。状态表示与转移用dist[u]表示到达机场uuu的最早绝对时间从起点出发时刻算起。初始dist[S] 0。当从机场uuu出发时必须等待boarding[u]分钟才能登机因此可登机的最早绝对时刻为ready dist[u] boarding[u]。计算ready时刻uuu的当地时间为L(t0ready(Δu−ΔS)) mod 1440 L (t_0 ready (\Delta_u - \Delta_S)) \bmod 1440L(t0​ready(Δu​−ΔS​))mod1440对于uuu的每个航班fff起飞当地时间dep飞行时长dur需找到最早的一次起飞可能当天或之后数天满足该次起飞当地时间为dep且不早于L。等待时间wait (dep - L) mod 1440结果非负则起飞绝对时刻depAbs ready wait到达目的地vvv的绝对时刻为depAbs dur。如果该值小于dist[v]则更新。注意由于飞行时长正数且等待时间非负图中边权非负可使用 Dijkstra 算法。节点最多100100100个边数最多约3×1043 \times 10^43×104优先队列Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra效率足够。路径回溯在更新dist[v]时同时记录前驱节点prevNode[v]以及所使用的航班标识符prevFlight[v]。当Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra结束从终点逆向回溯即可得到完整航班序列再反转输出。复杂度分析设机场数为NNN≤100\le 100≤100每个机场航班数最多MMM≤300\le 300≤300总边数E≤3×104E \le 3\times 10^4E≤3×104。Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra使用优先队列每次松弛操作O(log⁡N)O(\log N)O(logN)总复杂度O(Elog⁡N)O(E \log N)O(ElogN)远小于可接受范围。代码实现// Flying Stars// UVa ID: 771// Verdict: Accepted// Submission Date: 2026-07-08// UVa Run Time: 0.020s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 解析 hh:mm 为分钟数intparseTime(conststrings){inthstoi(s.substr(0,2));intmstoi(s.substr(3,2));returnh*60m;}// 解析时区 hh:mm 或 -hh:mm 为分钟偏移intparseTimezone(conststrings){intsign(s[0])?1:-1;inthstoi(s.substr(1,2));intmstoi(s.substr(4,2));returnsign*(h*60m);}// 将分钟数格式化为 hh:mm0~1439stringformatTime(intt){t%1440;if(t0)t1440;charbuf[6];sprintf(buf,%02d:%02d,t/60,t%60);returnstring(buf);}// 将总分钟数格式化为 d:hh:mmstringformatDuration(inttotal){intdaystotal/1440;intremtotal%1440;charbuf[20];sprintf(buf,%d:%02d:%02d,days,rem/60,rem%60);returnstring(buf);}structFlight{string id;string dest;intdep;// 本地起飞时间分钟 (0~1439)intdur;// 飞行时长分钟};structAirport{string id;intoffset;// 时区偏移分钟intboarding;// 登机/转机耗时分钟vectorFlightflights;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string srcId,dstId,startStr;boolfirstCasetrue;while(cinsrcIddstIdstartStr){if(!firstCase)cout\n;firstCasefalse;intN;cinN;unordered_mapstring,intidx;vectorAirportairports(N);for(inti0;iN;i){string id,tz,boardStr;intM;cinidtzboardStrM;idx[id]i;airports[i].idid;airports[i].offsetparseTimezone(tz);airports[i].boardingparseTime(boardStr);airports[i].flights.resize(M);for(intj0;jM;j){string fid,dest,depStr,durStr;cinfiddestdepStrdurStr;airports[i].flights[j].idfid;airports[i].flights[j].destdest;airports[i].flights[j].depparseTime(depStr);airports[i].flights[j].durparseTime(durStr);}}intsrcidx[srcId];intdstidx[dstId];intstartLocalparseTime(startStr);intoffsetSrcairports[src].offset;constintINF1e9;vectorintdist(N,INF);vectorintprevNode(N,-1);vectorstringprevFlight(N,);priority_queuepairint,int,vectorpairint,int,greaterpairint,intpq;dist[src]0;pq.push({0,src});while(!pq.empty()){auto[curDist,u]pq.top();pq.pop();if(curDist!dist[u])continue;if(udst)break;intreadycurDistairports[u].boarding;// 可登机绝对时间// 计算 ready 时刻该机场的本地时间intlocalReady(startLocalready(airports[u].offset-offsetSrc))%1440;if(localReady0)localReady1440;for(constFlightf:airports[u].flights){intwait(f.dep-localReady)%1440;if(wait0)wait1440;intdepAbsreadywait;intarrAbsdepAbsf.dur;intvidx[f.dest];if(arrAbsdist[v]){dist[v]arrAbs;prevNode[v]u;prevFlight[v]f.id;pq.push({arrAbs,v});}}}// 输出总旅行时间coutformatDuration(dist[dst])\n;// 输出到达目的地当地时间intarrivalLocal(startLocaldist[dst](airports[dst].offset-offsetSrc))%1440;if(arrivalLocal0)arrivalLocal1440;coutformatTime(arrivalLocal)\n;// 回溯路径vectorstringroute;intcurdst;while(cur!src){route.push_back(prevFlight[cur]);curprevNode[cur];}reverse(route.begin(),route.end());for(conststringfid:route)coutfid\n;}return0;}总结本题将时区、航班周期和转机等待时间整合到一个绝对时间轴上通过Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra算法求解最短路径。关键点在于将本地时间与绝对时间相互转换以及正确处理航班时刻的循环等待。该解法能够处理最多100100100个机场、300300300个航班的数据规模时间复杂度O(Elog⁡N)O(E \log N)O(ElogN)空间复杂度O(NE)O(N E)O(NE)满足题目要求。在实际实现中注意所有时间运算以分钟为单位避免浮点误差并严格处理模运算的负数情况。