企业官网建设流程全解析

题目描述

秘密特工Maria\texttt{Maria}Maria被派往Algorithms City\texttt{Algorithms City}Algorithms City执行任务。该城市的地铁系统只有一条线路，列车双向运行。Maria\texttt{Maria}Maria从第111站出发，需要准时到达第NNN站与接头人会面。由于在车站等待时面临被抓获的风险，她希望尽可能多地待在行驶的列车上，即使这意味着来回乘坐。给定列车时刻表，要求计算Maria\texttt{Maria}Maria在最佳乘车方案下，在车站等待的总时间。若无法准时到达，则输出impossible\texttt{impossible}impossible。

输入格式

输入包含多组测试数据。每组数据由777行组成。第111行是整数NNN（2≤N≤502 \le N \le 502≤N≤50），表示车站数量。第222行是整数TTT（0≤T≤2000 \le T \le 2000≤T≤200），表示会面时间。第333行包含N−1N-1N−1个整数t1,t2,…,tN−1t_1, t_2, \dots, t_{N-1}t1​,t2​,…,tN−1​（1≤ti≤201 \le t_i \le 201≤ti​≤20），表示相邻车站之间的列车行驶时间。第444行是整数M1M1M1（1≤M1≤501 \le M1 \le 501≤M1≤50），表示从第111站出发的列车数量。第555行包含M1M1M1个整数d1,d2,…,dM1d_1, d_2, \dots, d_{M1}d1​,d2​,…,dM1​（0≤di≤2500 \le d_i \le 2500≤di​≤250，di<di+1d_i < d_{i+1}di​<di+1​），表示从第111站出发的时刻。第666行是整数M2M2M2（1≤M2≤501 \le M2 \le 501≤M2≤50），表示从第NNN站出发的列车数量。第777行包含M2M2M2个整数e1,e2,…,eM2e_1, e_2, \dots, e_{M2}e1​,e2​,…,eM2​（0≤ei≤2500 \le e_i \le 2500≤ei​≤250，ei<ei+1e_i < e_{i+1}ei​<ei+1​），表示从第NNN站出发的时刻。输入以单独一行的数字000结束。

输出格式

对于每组测试数据，输出一行，包含测试数据编号（从111开始）以及最佳方案下的总等待时间（整数），若无法准时到达则输出impossible\texttt{impossible}impossible。格式为Case Number X: Y。

样例输入

4 55 5 10 15 4 0 5 10 20 4 0 5 10 15 4 18 1 2 3 5 0 3 6 10 12 6 0 3 5 7 12 15 2 30 20 1 20 7 1 3 5 7 11 13 17 0

样例输出

Case Number 1: 5 Case Number 2: 0 Case Number 3: impossible

题目分析

该问题可以建模为在时间-车站二维状态空间上的最短路径问题。状态由当前所在车站iii（1≤i≤N1 \le i \le N1≤i≤N）和当前时间jjj（0≤j≤T0 \le j \le T0≤j≤T）唯一确定。Maria\texttt{Maria}Maria可以在状态之间转移：若她在车站iii且时刻jjj，她可以选择等待，转移到同一车站的时刻j+1j+1j+1，等待时间增加111；若在时刻jjj恰有列车停靠车站iii，她可以乘坐该列车，在不增加等待时间的情况下转移到下一站（或上一站）的对应到达时刻。目标是从状态(1,0)(1, 0)(1,0)到达状态(N,T)(N, T)(N,T)的最小等待时间。由于状态空间规模为N×(T+1)≤50×201=10050N \times (T+1) \le 50 \times 201 = 10050N×(T+1)≤50×201=10050，可以使用Dijkstra\texttt{Dijkstra}Dijkstra算法求解。首先根据给定的列车出发时刻和站间行驶时间，预处理出每个车站在每个时刻是否有列车停靠以及乘坐列车可到达的下一状态。然后从初始状态运行Dijkstra\texttt{Dijkstra}Dijkstra，最终检查终点状态是否可达。

解题思路

对于每组数据，首先读取NNN、TTT、各站间行驶时间、从第111站出发的列车时刻、从第NNN站出发的列车时刻。为每个状态(i,j)(i, j)(i,j)分配一个唯一的编号。根据从第111站出发的列车时刻，计算每列列车到达各站的时刻，若不超过TTT，则记录该站该时刻有列车停靠，并建立从该站该时刻到后续各站对应到达时刻的零费用边（表示乘坐列车不增加等待时间）。同理，根据从第NNN站出发的列车时刻，建立反向的零费用边。然后，对于每个车站，将其所有有列车停靠的时刻按时间排序，相邻时刻之间建立等待边，费用为时间差。特别地，在起点(1,0)(1, 0)(1,0)和终点(N,T)(N, T)(N,T)添加必要的停靠时刻。最后，从起点状态运行Dijkstra\texttt{Dijkstra}Dijkstra，计算到达终点状态的最小等待时间。若终点状态的距离为无穷大，则输出impossible\texttt{impossible}impossible；否则输出该距离。

代码实现

// A Spy in the Metro// UVa ID: 1025// Verdict: Accepted// Submission Date: 2019-02-21// UVa Run Time: 0.010s//// 版权所有（C）2019，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintINF=0x7f7f7f7f;structedge{intv,w;edge(intv=0,intw=0):v(v),w(w){}booloperator<(constedge&e)const{returnw>e.w;}};vector<edge>edges[10010];vector<int>stopTime[60];intmapping[60][210],dist[10010];voidmooreDijkstra(){memset(dist,0x7f,sizeof(dist));priority_queue<edge>q;dist[0]=0;q.push(edge(0,0));while(!q.empty()){edge e1=q.top();q.pop();if(dist[e1.v]<e1.w)continue;for(autoe2:edges[e1.v]){if(dist[e2.v]>dist[e1.v]+e2.w){dist[e2.v]=dist[e1.v]+e2.w;q.push(edge(e2.v,dist[e2.v]));}}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0;intN,T,M1,M2;intforward[60],backward[60];while(cin>>N,N>0){cin>>T;intC=0;for(inti=1;i<=N;i++)for(intj=0;j<=T;j++){mapping[i][j]=C++;edges[mapping[i][j]].clear();}forward[1]=0;for(inti=2,t1;i<=N;i++){cin>>t1;forward[i]=forward[i-1]+t1;}backward[N]=0;for(inti=N-1;i>=1;i--)backward[i]=forward[N]-forward[i];for(inti=1;i<=N;i++)stopTime[i].clear();cin>>M1;for(inti=1,d1;i<=M1;i++){cin>>d1;for(intj=1;j<=N;j++){if(d1+forward[j]<=T)stopTime[j].push_back(d1+forward[j]);for(intk=j+1;k<=N;k++){if(d1+forward[j]<=T&&d1+forward[k]<=T)edges[mapping[j][d1+forward[j]]].push_back(edge(mapping[k][d1+forward[k]],0));}}}cin>>M2;for(inti=1,e1;i<=M2;i++){cin>>e1;for(intj=N;j>=1;j--){if(e1+backward[j]<=T)stopTime[j].push_back(e1+backward[j]);for(intk=j-1;k>=1;k--){if(e1+backward[j]<=T&&e1+backward[k]<=T)edges[mapping[j][e1+backward[j]]].push_back(edge(mapping[k][e1+backward[k]],0));}}}stopTime[1].push_back(0);stopTime[N].push_back(T);for(inti=1;i<=N;i++){sort(stopTime[i].begin(),stopTime[i].end());stopTime[i].erase(unique(stopTime[i].begin(),stopTime[i].end()),stopTime[i].end());}for(inti=0;i<=N;i++){inttot=stopTime[i].size();for(intj=0;j<tot-1;j++)for(intk=j+1;k<tot;k++){intt1=stopTime[i][j],t2=stopTime[i][k];edges[mapping[i][t1]].push_back(edge(mapping[i][t2],t2-t1));}}mooreDijkstra();intD=dist[mapping[N][T]];cout<<"Case Number "<<++cases<<": ";if(D==INF)cout<<"impossible\n";elsecout<<D<<'\n';}return0;}

总结

本题的关键在于将时间-车站状态建模为图的最短路径问题，并利用Dijkstra\texttt{Dijkstra}Dijkstra算法求解最小等待时间。通过预处理列车时刻表，构建状态之间的零费用转移边（乘坐列车）和正费用转移边（等待），可以准确地描述Maria\texttt{Maria}Maria的所有可能行动。注意处理起点和终点的特殊停靠时刻，以及状态空间的合理映射。掌握时间-状态图建模与最短路径算法，对于解决此类调度与路径规划问题具有重要的参考价值。