![打卡信奥刷题（3306）用C++实现信奥题 P9126 [USACO23FEB] Moo Route II S](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3306）用C++实现信奥题 P9126 [USACO23FEB] Moo Route II S)
P9126 [USACO23FEB] Moo Route II S题目描述注意本题的时间限制为 4 秒是默认限制的两倍。Bessie 正在度假由于最近的技术进步Bessie 可以通过先进的航班旅行这些航班甚至可以进行时间旅行。此外即使存在多个“平行”的 Bessie 同时出现也不会有任何问题。在这个国家有NNN个机场编号为1,2,⋯ ,N1,2,\cdots,N1,2,⋯,N以及MMM条时间旅行航班1≤N,M≤2×1051 \leq N,M \leq 2 \times 10^51≤N,M≤2×105。第jjj条航班从机场cjc_jcj在时间rjr_jrj起飞并在时间sjs_jsj抵达机场djd_jdj0≤rj,sj≤1090 \leq r_j,s_j \leq 10^90≤rj,sj≤109sjrjs_j r_jsjrj是可能的。此外Bessie 在机场iii需要停留aia_iai时间1≤ai≤1091 \leq a_i \leq 10^91≤ai≤109。也就是说如果 Bessie 乘坐一趟航班在时间sss抵达机场iii她可以转乘一趟从该机场出发的航班只要该航班的起飞时间r≥sair \geq s a_ir≥sai。需要注意的是停留时间不会影响 Bessie 抵达某机场的实际时间。Bessie 从机场111出发起始时间为000。对于从111到NNN的每个机场求出 Bessie 最早可以到达该机场的时间。输入格式第一行输入包含两个整数NNN和MMM。接下来的MMM行描述航班信息。其中第jjj行包含cj,rj,dj,sjc_j, r_j, d_j, s_jcj,rj,dj,sj依次表示航班的起飞机场、起飞时间、降落机场和降落时间。(1≤cj,dj≤N,0≤rj,sj≤109)(1 \leq c_j,d_j \leq N, 0 \leq r_j,s_j \leq 10^9)(1≤cj,dj≤N,0≤rj,sj≤109)接下来的111行描述每个机场的停留时间。该行包含NNN个用空格分隔的整数分别为a1,⋯ ,aNa_1,\cdots,a_Na1,⋯,aN。输出格式输出共NNN行。第iii行输出 Bessie 最早到达机场iii的时间如果无法到达该机场输出−1-1−1。输入输出样例 #1输入 #13 3 1 0 2 10 2 11 2 0 2 1 3 20 10 1 10输出 #10 0 20输入输出样例 #2输入 #23 3 1 0 2 10 2 10 2 0 2 1 3 20 10 1 10输出 #20 10 -1说明/提示样例 1 的解释Bessie 可以按照给定的顺序乘坐333班航班这使她可以在时间000到达机场111和机场222以及在时间202020到达机场333。注意这条路线会两次经过机场222第一次是在时间10−1110-1110−11第二次是在时间0−10-10−1。样例 2 的解释在这个例子中Bessie 可以乘坐第111班航班在时间101010抵达机场222。但是她无法及时赶上第222班航班因为该航班的起飞时间为101010而她需要至少111个时间单位来完成停留。评分标准测试点3−53-53−5对于每个jjjrjsjr_j s_jrjsj也就是说所有航班的到达时间晚于起飞时间。测试点6−106-106−10N,M≤5000N,M \leq 5000N,M≤5000测试点11−2011-2011−20无额外限制。C实现#includevector#includeiostream#includealgorithmusingnamespacestd;intn,m,c;inte[200005],f[200005],dis[200005];structPlane{intr,d,s;}t;boolcmp(Plane p1,Plane p2){returnp1.rp2.r;}vectorPlanev[200005];voiddfs(intx,intti){for(intif[x];i0;i--){tv[x][i];if(tit.r)break;elseif(i0)f[x]-1;dis[t.d]min(dis[t.d],t.s);f[x]i-1;dfs(t.d,t.se[t.d]);}}intmain(){for(inti1;i200000;i)dis[i]1000000001;scanf(%d%d,n,m);for(inti1;im;i){scanf(%d%d%d%d,c,t.r,t.d,t.s);v[c].push_back(t);}for(inti1;in;i){scanf(%d,e[i]);f[i]v[i].size()-1;sort(v[i].begin(),v[i].end(),cmp);}dis[1]0;dfs(1,0);for(inti1;in;i){if(dis[i]1000000001)cout-1\n;elsecoutdis[i]\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3306）用C++实现信奥题 P9126 [USACO23FEB] Moo Route II S
发布时间：2026/5/23 14:08:07
P9126 [USACO23FEB] Moo Route II S题目描述注意本题的时间限制为 4 秒是默认限制的两倍。Bessie 正在度假由于最近的技术进步Bessie 可以通过先进的航班旅行这些航班甚至可以进行时间旅行。此外即使存在多个“平行”的 Bessie 同时出现也不会有任何问题。在这个国家有NNN个机场编号为1,2,⋯ ,N1,2,\cdots,N1,2,⋯,N以及MMM条时间旅行航班1≤N,M≤2×1051 \leq N,M \leq 2 \times 10^51≤N,M≤2×105。第jjj条航班从机场cjc_jcj在时间rjr_jrj起飞并在时间sjs_jsj抵达机场djd_jdj0≤rj,sj≤1090 \leq r_j,s_j \leq 10^90≤rj,sj≤109sjrjs_j r_jsjrj是可能的。此外Bessie 在机场iii需要停留aia_iai时间1≤ai≤1091 \leq a_i \leq 10^91≤ai≤109。也就是说如果 Bessie 乘坐一趟航班在时间sss抵达机场iii她可以转乘一趟从该机场出发的航班只要该航班的起飞时间r≥sair \geq s a_ir≥sai。需要注意的是停留时间不会影响 Bessie 抵达某机场的实际时间。Bessie 从机场111出发起始时间为000。对于从111到NNN的每个机场求出 Bessie 最早可以到达该机场的时间。输入格式第一行输入包含两个整数NNN和MMM。接下来的MMM行描述航班信息。其中第jjj行包含cj,rj,dj,sjc_j, r_j, d_j, s_jcj,rj,dj,sj依次表示航班的起飞机场、起飞时间、降落机场和降落时间。(1≤cj,dj≤N,0≤rj,sj≤109)(1 \leq c_j,d_j \leq N, 0 \leq r_j,s_j \leq 10^9)(1≤cj,dj≤N,0≤rj,sj≤109)接下来的111行描述每个机场的停留时间。该行包含NNN个用空格分隔的整数分别为a1,⋯ ,aNa_1,\cdots,a_Na1,⋯,aN。输出格式输出共NNN行。第iii行输出 Bessie 最早到达机场iii的时间如果无法到达该机场输出−1-1−1。输入输出样例 #1输入 #13 3 1 0 2 10 2 11 2 0 2 1 3 20 10 1 10输出 #10 0 20输入输出样例 #2输入 #23 3 1 0 2 10 2 10 2 0 2 1 3 20 10 1 10输出 #20 10 -1说明/提示样例 1 的解释Bessie 可以按照给定的顺序乘坐333班航班这使她可以在时间000到达机场111和机场222以及在时间202020到达机场333。注意这条路线会两次经过机场222第一次是在时间10−1110-1110−11第二次是在时间0−10-10−1。样例 2 的解释在这个例子中Bessie 可以乘坐第111班航班在时间101010抵达机场222。但是她无法及时赶上第222班航班因为该航班的起飞时间为101010而她需要至少111个时间单位来完成停留。评分标准测试点3−53-53−5对于每个jjjrjsjr_j s_jrjsj也就是说所有航班的到达时间晚于起飞时间。测试点6−106-106−10N,M≤5000N,M \leq 5000N,M≤5000测试点11−2011-2011−20无额外限制。C实现#includevector#includeiostream#includealgorithmusingnamespacestd;intn,m,c;inte[200005],f[200005],dis[200005];structPlane{intr,d,s;}t;boolcmp(Plane p1,Plane p2){returnp1.rp2.r;}vectorPlanev[200005];voiddfs(intx,intti){for(intif[x];i0;i--){tv[x][i];if(tit.r)break;elseif(i0)f[x]-1;dis[t.d]min(dis[t.d],t.s);f[x]i-1;dfs(t.d,t.se[t.d]);}}intmain(){for(inti1;i200000;i)dis[i]1000000001;scanf(%d%d,n,m);for(inti1;im;i){scanf(%d%d%d%d,c,t.r,t.d,t.s);v[c].push_back(t);}for(inti1;in;i){scanf(%d,e[i]);f[i]v[i].size()-1;sort(v[i].begin(),v[i].end(),cmp);}dis[1]0;dfs(1,0);for(inti1;in;i){if(dis[i]1000000001)cout-1\n;elsecoutdis[i]\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
