题目分析本题是一个带有时间约束的最短路径问题。我们需要在给定的航班列表中为每次旅行请求找到最优路线。优化目标可以是最小化总费用或最小化总旅行时间。如果存在多条最优路线同样最小化费用或时间则进一步比较另一个目标选择更优的那一条。主要特点航班信息包含起点、终点、出发时间、到达时间、费用。时间格式为HH:MMX其中X为A上午或P下午。出发时间总是早于到达时间且单次航班时长小于242424小时。最多505050条航班最多202020个城市。总旅行时间小于101010天144001440014400分钟总费用小于 $1000.001000.001000.00。城市名称不区分大小写但输出时首字母需大写。输入由多个测试用例组成每个用例以TRAVEL XXX开头航班段和请求段均以#结束。解题思路1. 数据存储与预处理使用mapstring, int将城市名称映射到整数索引便于图的操作。使用邻接表vectorvectoredge存储航班信息。将时间字符串转换为从00:00开始的分钟数便于计算时间差。将费用字符串转换为整数以“分”为单位避免浮点数误差。2. 时间与费用计算getTime()将时间字符串转换为分钟数注意P表示下午需加720720720分钟。getCost()将费用字符串转换为整数分删除小数点后转换为整数。interval()计算两个时间点之间的分钟差考虑跨午夜的情况。wait()计算等待时间同样考虑跨午夜。3. 算法选择由于城市数量少≤20\le 20≤20航班数量有限≤50\le 50≤50且题目保证有唯一解我们可以使用DFS\texttt{DFS}DFS回溯来枚举所有可能的路径。回溯函数backtrack(start, end, index)的参数start当前所在城市的索引end目标城市的索引index当前路径中的航班数量剪枝条件如果当前累计时间≥14400\ge 14400≥14400分钟或累计费用≥100000\ge 100000≥100000分则停止搜索。使用visited[]数组防止形成环。4. 最优解比较根据当前请求的优化目标costFirst标志进行判断若优化费用优先比较totalCost相同时比较totalTime。若优化时间优先比较totalTime相同时比较totalCost。5. 特殊情况处理起点和终点相同输出You are already in X.起点或终点不在任何航班中出现输出There is no route from X to Y.6. 输出格式每个测试用例输出标题Requests and optimal routes for travel X和分隔线。不同请求之间空一行不同测试用例之间空两行。路径需按顺序输出每一段航班的起点、终点、出发时间、到达时间、费用。最后一行输出总时间和总费用右对齐。代码实现// Getting There// UVa ID: 205// Verdict: Accepted// Submission Date: 2016-04-23// UVa Run Time: 0.030s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structedge{string startCity,endCity,leaveTime,arriveTime,costMoney;intstart,end,leave,arrive,time,cost;};vectorvectoredgeedges;mapstring,intcityIndexs;vectorstringcityNames;setstringstartCities,endCities;boolfound;vectoredgepath,best;vectorboolvisited;intbestTime14400,bestCost100000;boolcostFirst;// 计算等待时间从到达时间到下一次出发时间考虑跨午夜intwait(intarrive,intleave){if(leavearrive)returnleave-arrive;elsereturn(1440-(arrive-leave));}// 计算飞行时间从出发到到达考虑跨午夜intinterval(intleave,intarrive){if(arriveleave)returnarrive-leave;elsereturn(1440-(leave-arrive));}// DFS 回溯搜索所有路径voidbacktrack(intstart,intend,intindex){// 到达目标城市if(startend){inttotalTime0,totalCost0;for(inti0;iindex;i){totalTimepath[i].time;totalCostpath[i].cost;if(i0)totalTimewait(path[i-1].arrive,path[i].leave);}// 剪枝超出限制if(totalTime14400||totalCost100000)return;// 根据优化目标判断是否更优if((costFirst(totalCostbestCost||(totalCostbestCosttotalTimebestTime)))||(!costFirst(totalTimebestTime||(totalTimebestTimetotalCostbestCost)))){best.clear();for(inti0;iindex;i)best.push_back(path[i]);bestTimetotalTime;bestCosttotalCost;foundtrue;}return;}// 遍历所有从当前城市出发的航班for(inti0;iedges[start].size();i)// 避免环路if(visited[edges[start][i].end]false){visited[edges[start][i].end]true;path[index]edges[start][i];backtrack(edges[start][i].end,end,index1);visited[edges[start][i].end]false;}}// 将字符串转为小写用于统一城市名stringtoLower(string source){for(inti0;isource.length();i)source[i]tolower(source[i]);returnsource;}// 将字符串首字母大写用于输出stringtoUpper(string source){source[0]toupper(source[0]);returnsource;}// 将时间字符串转换为分钟数intgetTime(string time){intminutes0;intindexertime.find(:);minutesstoi(time.substr(0,indexer))*60;minutesstoi(time.substr(indexer1,2));if(time.back()P)minutes720;returnminutes;}// 将费用字符串转换为整数分intgetCost(string cost){for(inti0;icost.length();i)if(cost[i].){cost.erase(cost.begin()i);break;}returnstoi(cost);}// 将分钟数转换为时间字符串如 1 day 4:35stringtoTime(inttime){string text;intdaystime/1440;if(days2){textto_string(days);text days ;}elseif(days1){textto_string(days);text day ;}time%1440;textto_string(time/60);text:;time%60;texttime10?:0;textto_string(time);returntext;}// 将整数分转换为货币字符串stringtoCost(intcost){string text$;textto_string(cost/100);text.;cost%100;textcost10?:0;textto_string(cost);returntext;}// 去除时间字符串中小时部分的 leading zerostringtrimTime(string time){if(time[0]0time[1]!:)time.erase(time.begin());returntime;}intmain(){cin.tie(0);cout.sync_with_stdio(false);string line;boolprintTwoBlankLinefalse;while(getline(cin,line)){edges.clear();cityIndexs.clear();cityNames.clear();startCities.clear();endCities.clear();// 最多 20 个城市edges.resize(20);visited.resize(20);path.resize(20);istringstreamiss(line);string firstPart,secondPart;issfirstPartsecondPart;// 输出两个空行分隔测试用例if(printTwoBlankLine)cout\n\n;elseprintTwoBlankLinetrue;coutRequests and optimal routes for travel ;coutstoi(secondPart)\n;cout------------------------------------------\n;cout\n;// 读取航班信息直到 #while(getline(cin,line),line!#){edge aEdge;string startCity,endCity,leaveTime,arriveTime,costMoney;iss.clear();iss.str(line);issstartCityendCityleaveTimearriveTimecostMoney;// 统一为小写处理startCitytoLower(startCity);endCitytoLower(endCity);if(cityIndexs.count(startCity)0){cityNames.push_back(startCity);cityIndexs.insert({startCity,cityNames.size()-1});}if(cityIndexs.count(endCity)0){cityNames.push_back(endCity);cityIndexs.insert({endCity,cityNames.size()-1});}startCities.insert(startCity);endCities.insert(endCity);// 构造边aEdge.startCitytoUpper(startCity);aEdge.endCitytoUpper(endCity);aEdge.startcityIndexs[startCity];aEdge.endcityIndexs[endCity];aEdge.leaveTimetrimTime(leaveTime);aEdge.arriveTimetrimTime(arriveTime);aEdge.leavegetTime(leaveTime);aEdge.arrivegetTime(arriveTime);aEdge.timeinterval(aEdge.leave,aEdge.arrive);aEdge.costgetCost(costMoney);aEdge.costMoneytoCost(aEdge.cost);edges[aEdge.start].push_back(aEdge);}boolprintOneBlankLinefalse;// 处理旅行请求直到 #while(getline(cin,line),line!#){string startCity,endCity,target;iss.clear();iss.str(line);issstartCityendCitytarget;startCitytoLower(startCity);endCitytoLower(endCity);// 请求之间空一行if(printOneBlankLine)cout\n;elseprintOneBlankLinetrue;// 起点与终点相同if(startCityendCity){coutYou are already in toUpper(startCity).\n;continue;}// 城市不存在于任何航班中if(startCities.count(startCity)0||endCities.count(endCity)0){coutThere is no route from ;couttoUpper(startCity);cout to ;couttoUpper(endCity);cout.\n;continue;}// DFS 回溯搜索最优路线foundfalse;costFirsttargetCOST;bestTime14400;bestCost100000;fill(visited.begin(),visited.end(),false);backtrack(cityIndexs[startCity],cityIndexs[endCity],0);// 输出结果if(found){// 输出请求信息coutFrom: ;coutsetw(21)lefttoUpper(startCity);coutTo: ;coutsetw(21)lefttoUpper(endCity);coutOptimize: ;couttoUpper(toLower(target));cout\n;// 表头cout\n;coutsetw(20)leftFrom;coutsetw(23)leftTo;coutsetw(8)leftLeave;coutsetw(6)leftArrive;coutsetw(9)rightCost;cout\n;cout\n;// 输出每一段航班for(inti0;ibest.size();i){coutsetw(20)leftbest[i].startCity;coutsetw(23)leftbest[i].endCity;coutsetw(8)leftbest[i].leaveTime;coutsetw(6)leftbest[i].arriveTime;coutsetw(9)rightbest[i].costMoney;cout\n;}// 输出总时间和总费用coutsetw(66)right-----------------------;cout\n;coutsetw(57)righttoTime(bestTime);coutsetw(9)righttoCost(bestCost);cout\n;}else{coutThere is no route from ;couttoUpper(startCity);cout to ;couttoUpper(endCity);cout.\n;}}}return0;}总结本题的核心在于处理跨午夜的时间计算以及在有约束条件下的多目标最优路径搜索。由于数据规模较小使用DFS\texttt{DFS}DFS回溯即可在时间限制内完成搜索。代码中需要仔细处理输入格式、时间转换和输出对齐确保与样例输出完全一致。
UVa 205 Getting There
题目分析本题是一个带有时间约束的最短路径问题。我们需要在给定的航班列表中为每次旅行请求找到最优路线。优化目标可以是最小化总费用或最小化总旅行时间。如果存在多条最优路线同样最小化费用或时间则进一步比较另一个目标选择更优的那一条。主要特点航班信息包含起点、终点、出发时间、到达时间、费用。时间格式为HH:MMX其中X为A上午或P下午。出发时间总是早于到达时间且单次航班时长小于242424小时。最多505050条航班最多202020个城市。总旅行时间小于101010天144001440014400分钟总费用小于 $1000.001000.001000.00。城市名称不区分大小写但输出时首字母需大写。输入由多个测试用例组成每个用例以TRAVEL XXX开头航班段和请求段均以#结束。解题思路1. 数据存储与预处理使用mapstring, int将城市名称映射到整数索引便于图的操作。使用邻接表vectorvectoredge存储航班信息。将时间字符串转换为从00:00开始的分钟数便于计算时间差。将费用字符串转换为整数以“分”为单位避免浮点数误差。2. 时间与费用计算getTime()将时间字符串转换为分钟数注意P表示下午需加720720720分钟。getCost()将费用字符串转换为整数分删除小数点后转换为整数。interval()计算两个时间点之间的分钟差考虑跨午夜的情况。wait()计算等待时间同样考虑跨午夜。3. 算法选择由于城市数量少≤20\le 20≤20航班数量有限≤50\le 50≤50且题目保证有唯一解我们可以使用DFS\texttt{DFS}DFS回溯来枚举所有可能的路径。回溯函数backtrack(start, end, index)的参数start当前所在城市的索引end目标城市的索引index当前路径中的航班数量剪枝条件如果当前累计时间≥14400\ge 14400≥14400分钟或累计费用≥100000\ge 100000≥100000分则停止搜索。使用visited[]数组防止形成环。4. 最优解比较根据当前请求的优化目标costFirst标志进行判断若优化费用优先比较totalCost相同时比较totalTime。若优化时间优先比较totalTime相同时比较totalCost。5. 特殊情况处理起点和终点相同输出You are already in X.起点或终点不在任何航班中出现输出There is no route from X to Y.6. 输出格式每个测试用例输出标题Requests and optimal routes for travel X和分隔线。不同请求之间空一行不同测试用例之间空两行。路径需按顺序输出每一段航班的起点、终点、出发时间、到达时间、费用。最后一行输出总时间和总费用右对齐。代码实现// Getting There// UVa ID: 205// Verdict: Accepted// Submission Date: 2016-04-23// UVa Run Time: 0.030s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structedge{string startCity,endCity,leaveTime,arriveTime,costMoney;intstart,end,leave,arrive,time,cost;};vectorvectoredgeedges;mapstring,intcityIndexs;vectorstringcityNames;setstringstartCities,endCities;boolfound;vectoredgepath,best;vectorboolvisited;intbestTime14400,bestCost100000;boolcostFirst;// 计算等待时间从到达时间到下一次出发时间考虑跨午夜intwait(intarrive,intleave){if(leavearrive)returnleave-arrive;elsereturn(1440-(arrive-leave));}// 计算飞行时间从出发到到达考虑跨午夜intinterval(intleave,intarrive){if(arriveleave)returnarrive-leave;elsereturn(1440-(leave-arrive));}// DFS 回溯搜索所有路径voidbacktrack(intstart,intend,intindex){// 到达目标城市if(startend){inttotalTime0,totalCost0;for(inti0;iindex;i){totalTimepath[i].time;totalCostpath[i].cost;if(i0)totalTimewait(path[i-1].arrive,path[i].leave);}// 剪枝超出限制if(totalTime14400||totalCost100000)return;// 根据优化目标判断是否更优if((costFirst(totalCostbestCost||(totalCostbestCosttotalTimebestTime)))||(!costFirst(totalTimebestTime||(totalTimebestTimetotalCostbestCost)))){best.clear();for(inti0;iindex;i)best.push_back(path[i]);bestTimetotalTime;bestCosttotalCost;foundtrue;}return;}// 遍历所有从当前城市出发的航班for(inti0;iedges[start].size();i)// 避免环路if(visited[edges[start][i].end]false){visited[edges[start][i].end]true;path[index]edges[start][i];backtrack(edges[start][i].end,end,index1);visited[edges[start][i].end]false;}}// 将字符串转为小写用于统一城市名stringtoLower(string source){for(inti0;isource.length();i)source[i]tolower(source[i]);returnsource;}// 将字符串首字母大写用于输出stringtoUpper(string source){source[0]toupper(source[0]);returnsource;}// 将时间字符串转换为分钟数intgetTime(string time){intminutes0;intindexertime.find(:);minutesstoi(time.substr(0,indexer))*60;minutesstoi(time.substr(indexer1,2));if(time.back()P)minutes720;returnminutes;}// 将费用字符串转换为整数分intgetCost(string cost){for(inti0;icost.length();i)if(cost[i].){cost.erase(cost.begin()i);break;}returnstoi(cost);}// 将分钟数转换为时间字符串如 1 day 4:35stringtoTime(inttime){string text;intdaystime/1440;if(days2){textto_string(days);text days ;}elseif(days1){textto_string(days);text day ;}time%1440;textto_string(time/60);text:;time%60;texttime10?:0;textto_string(time);returntext;}// 将整数分转换为货币字符串stringtoCost(intcost){string text$;textto_string(cost/100);text.;cost%100;textcost10?:0;textto_string(cost);returntext;}// 去除时间字符串中小时部分的 leading zerostringtrimTime(string time){if(time[0]0time[1]!:)time.erase(time.begin());returntime;}intmain(){cin.tie(0);cout.sync_with_stdio(false);string line;boolprintTwoBlankLinefalse;while(getline(cin,line)){edges.clear();cityIndexs.clear();cityNames.clear();startCities.clear();endCities.clear();// 最多 20 个城市edges.resize(20);visited.resize(20);path.resize(20);istringstreamiss(line);string firstPart,secondPart;issfirstPartsecondPart;// 输出两个空行分隔测试用例if(printTwoBlankLine)cout\n\n;elseprintTwoBlankLinetrue;coutRequests and optimal routes for travel ;coutstoi(secondPart)\n;cout------------------------------------------\n;cout\n;// 读取航班信息直到 #while(getline(cin,line),line!#){edge aEdge;string startCity,endCity,leaveTime,arriveTime,costMoney;iss.clear();iss.str(line);issstartCityendCityleaveTimearriveTimecostMoney;// 统一为小写处理startCitytoLower(startCity);endCitytoLower(endCity);if(cityIndexs.count(startCity)0){cityNames.push_back(startCity);cityIndexs.insert({startCity,cityNames.size()-1});}if(cityIndexs.count(endCity)0){cityNames.push_back(endCity);cityIndexs.insert({endCity,cityNames.size()-1});}startCities.insert(startCity);endCities.insert(endCity);// 构造边aEdge.startCitytoUpper(startCity);aEdge.endCitytoUpper(endCity);aEdge.startcityIndexs[startCity];aEdge.endcityIndexs[endCity];aEdge.leaveTimetrimTime(leaveTime);aEdge.arriveTimetrimTime(arriveTime);aEdge.leavegetTime(leaveTime);aEdge.arrivegetTime(arriveTime);aEdge.timeinterval(aEdge.leave,aEdge.arrive);aEdge.costgetCost(costMoney);aEdge.costMoneytoCost(aEdge.cost);edges[aEdge.start].push_back(aEdge);}boolprintOneBlankLinefalse;// 处理旅行请求直到 #while(getline(cin,line),line!#){string startCity,endCity,target;iss.clear();iss.str(line);issstartCityendCitytarget;startCitytoLower(startCity);endCitytoLower(endCity);// 请求之间空一行if(printOneBlankLine)cout\n;elseprintOneBlankLinetrue;// 起点与终点相同if(startCityendCity){coutYou are already in toUpper(startCity).\n;continue;}// 城市不存在于任何航班中if(startCities.count(startCity)0||endCities.count(endCity)0){coutThere is no route from ;couttoUpper(startCity);cout to ;couttoUpper(endCity);cout.\n;continue;}// DFS 回溯搜索最优路线foundfalse;costFirsttargetCOST;bestTime14400;bestCost100000;fill(visited.begin(),visited.end(),false);backtrack(cityIndexs[startCity],cityIndexs[endCity],0);// 输出结果if(found){// 输出请求信息coutFrom: ;coutsetw(21)lefttoUpper(startCity);coutTo: ;coutsetw(21)lefttoUpper(endCity);coutOptimize: ;couttoUpper(toLower(target));cout\n;// 表头cout\n;coutsetw(20)leftFrom;coutsetw(23)leftTo;coutsetw(8)leftLeave;coutsetw(6)leftArrive;coutsetw(9)rightCost;cout\n;cout\n;// 输出每一段航班for(inti0;ibest.size();i){coutsetw(20)leftbest[i].startCity;coutsetw(23)leftbest[i].endCity;coutsetw(8)leftbest[i].leaveTime;coutsetw(6)leftbest[i].arriveTime;coutsetw(9)rightbest[i].costMoney;cout\n;}// 输出总时间和总费用coutsetw(66)right-----------------------;cout\n;coutsetw(57)righttoTime(bestTime);coutsetw(9)righttoCost(bestCost);cout\n;}else{coutThere is no route from ;couttoUpper(startCity);cout to ;couttoUpper(endCity);cout.\n;}}}return0;}总结本题的核心在于处理跨午夜的时间计算以及在有约束条件下的多目标最优路径搜索。由于数据规模较小使用DFS\texttt{DFS}DFS回溯即可在时间限制内完成搜索。代码中需要仔细处理输入格式、时间转换和输出对齐确保与样例输出完全一致。
