题目描述
给定若干机场以及每日循环的航班信息。每个机场有固定的时区偏移和登机 / 转机耗时。从起点机场的某个本地时刻出发，需要经过一系列航班抵达终点机场。要求计算从出发时刻到抵达终点时刻的总旅行时间（以天、小时、分钟表示），并输出抵达终点时的本地时间以及最优路径上各航班的标识符。
输入格式
每个测试用例由多行组成。第一行包含起点机场标识符、终点机场标识符和出发本地时间（格式hh:mm）。第二行是一个整数NNN（2≤N≤1002 \le N \le 1002≤N≤100），表示机场总数。接下来NNN个机场的描述，每个描述以标题行开始：机场标识符、时区（格式shh:mm，+或-）、登机耗时（格式hh:mm）和一个整数MMM（M≤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)=(t0+T+(Δ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=(t0+ready+(Δ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(logN)O(\log N)O(logN)，总复杂度O(ElogN)O(E \log N)O(ElogN)，远小于可接受范围。
代码实现
// Flying Stars// UVa ID: 771// Verdict: Accepted// Submission Date: 2026-07-08// UVa Run Time: 0.020s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 解析 "hh:mm" 为分钟数intparseTime(conststring&s){inth=stoi(s.substr(0,2));intm=stoi(s.substr(3,2));returnh*60+m;}// 解析时区 "+hh:mm" 或 "-hh:mm" 为分钟偏移intparseTimezone(conststring&s){intsign=(s[0]=='+')?1:-1;inth=stoi(s.substr(1,2));intm=stoi(s.substr(4,2));returnsign*(h*60+m);}// 将分钟数格式化为 "hh:mm"（0~1439）stringformatTime(intt){t%=1440;if(t<0)t+=1440;charbuf[6];sprintf(buf,"%02d:%02d",t/60,t%60);returnstring(buf);}// 将总分钟数格式化为 "d:hh:mm"stringformatDuration(inttotal){intdays=total/1440;intrem=total%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;// 登机/转机耗时，分钟vector<Flight>flights;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string srcId,dstId,startStr;boolfirstCase=true;while(cin>>srcId>>dstId>>startStr){if(!firstCase)cout<<'\n';firstCase=false;intN;cin>>N;unordered_map<string,int>idx;vector<Airport>airports(N);for(inti=0;i<N;++i){string id,tz,boardStr;intM;cin>>id>>tz>>boardStr>>M;idx[id]=i;airports[i].id=id;airports[i].offset=parseTimezone(tz);airports[i].boarding=parseTime(boardStr);airports[i].flights.resize(M);for(intj=0;j<M;++j){string fid,dest,depStr,durStr;cin>>fid>>dest>>depStr>>durStr;airports[i].flights[j].id=fid;airports[i].flights[j].dest=dest;airports[i].flights[j].dep=parseTime(depStr);airports[i].flights[j].dur=parseTime(durStr);}}intsrc=idx[srcId];intdst=idx[dstId];intstartLocal=parseTime(startStr);intoffsetSrc=airports[src].offset;constintINF=1e9;vector<int>dist(N,INF);vector<int>prevNode(N,-1);vector<string>prevFlight(N,"");priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;dist[src]=0;pq.push({0,src});while(!pq.empty()){auto[curDist,u]=pq.top();pq.pop();if(curDist!=dist[u])continue;if(u==dst)break;intready=curDist+airports[u].boarding;// 可登机绝对时间// 计算 ready 时刻该机场的本地时间intlocalReady=(startLocal+ready+(airports[u].offset-offsetSrc))%1440;if(localReady<0)localReady+=1440;for(constFlight&f:airports[u].flights){intwait=(f.dep-localReady)%1440;if(wait<0)wait+=1440;intdepAbs=ready+wait;intarrAbs=depAbs+f.dur;intv=idx[f.dest];if(arrAbs<dist[v]){dist[v]=arrAbs;prevNode[v]=u;prevFlight[v]=f.id;pq.push({arrAbs,v});}}}// 输出总旅行时间cout<<formatDuration(dist[dst])<<'\n';// 输出到达目的地当地时间intarrivalLocal=(startLocal+dist[dst]+(airports[dst].offset-offsetSrc))%1440;if(arrivalLocal<0)arrivalLocal+=1440;cout<<formatTime(arrivalLocal)<<'\n';// 回溯路径vector<string>route;intcur=dst;while(cur!=src){route.push_back(prevFlight[cur]);cur=prevNode[cur];}reverse(route.begin(),route.end());for(conststring&fid:route)cout<<fid<<'\n';}return0;}总结
本题将时区、航班周期和转机等待时间整合到一个绝对时间轴上，通过Moore-Dijkstra\texttt{Moore-Dijkstra}Moore-Dijkstra算法求解最短路径。关键点在于将本地时间与绝对时间相互转换，以及正确处理航班时刻的循环等待。该解法能够处理最多100100100个机场、300300300个航班的数据规模，时间复杂度O(ElogN)O(E \log N)O(ElogN)，空间复杂度O(N+E)O(N + E)O(N+E)，满足题目要求。在实际实现中，注意所有时间运算以分钟为单位，避免浮点误差，并严格处理模运算的负数情况。
