UVa 383 Shipping Routes

题目描述Slow Boat to China\texttt{Slow Boat to China}Slow Boat to China航运公司需要一个程序来帮助快速向潜在客户报价。运费取决于货物的大小和所需的运输段数。一个运输段连接两个仓库但并非所有仓库之间都有直接连接因此从一个仓库到另一个仓库可能需要多个运输段。每个数据集包含111到303030个仓库。每个仓库由两个大写字母标识。运输段是双向的存在于任意两个不同的仓库之间。运费 货物大小 × 所需运输段数 ×100100100。对于给定的运输请求货物大小、始发仓库、目的仓库程序输出最佳最便宜的运费如果无法运输则输出相应信息。输入格式第一行包含整数TTT1≤T≤101 \leq T \leq 101≤T≤10表示数据集中数据集的个数。每个数据集的第一行包含三个整数MMM1≤M≤301 \leq M \leq 301≤M≤30仓库数量NNN0≤N≤M(M−1)/20 \leq N \leq M(M-1)/20≤N≤M(M−1)/2运输段数量PPP0≤P≤100 \leq P \leq 100≤P≤10运输请求数量第二行包含MMM个两个字母的仓库代码大写字母以空格分隔。接下来NNN行每行包含两个仓库代码表示它们之间有直接运输段。接下来PPP行每行包含一个整数货物大小和两个仓库代码始发地和目的地。输出格式第一行输出SHIPPING ROUTES OUTPUT。对于每个数据集输出DATA SET X标题然后PPP行结果$cost或NO SHIPMENT POSSIBLE。最后一行输出END OF OUTPUT。样例输入2 6 7 5 AA CC QR FF DD AB AA CC CC QR DD CC AA DD AA AB DD QR AB DD 5 AA AB 14 DD CC 1 CC DD 2 AA FF 13 AB QR 3 0 1 AA BB CC 5 AA CC样例输出SHIPPING ROUTES OUTPUT DATA SET 1 $500 $1400 $100 NO SHIPMENT POSSIBLE $2600 DATA SET 2 NO SHIPMENT POSSIBLE END OF OUTPUT题目分析问题的本质这是一个图论最短路径问题。每个仓库是节点运输段是边权重为111。需要回答多个查询给定起点和终点求最短路径长度运输段数然后计算运费。算法选择节点数M≤30M \leq 30M≤30可以使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法计算所有点对之间的最短路径时间复杂度O(M3)27000O(M^3) 27000O(M3)27000完全可行或对每个查询使用BFS\texttt{BFS}BFS但P≤10P \leq 10P≤10MMM很小两种方法均可无连接处理如果两点之间不可达距离为无穷大输出NO SHIPMENT POSSIBLE。运费计算运费 货物大小 × 最短路径长度 ×100100100。参考代码// Shippint Routes// UVa ID: 383// Verdict: Accepted// Submission Date: 2016-06-28// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_LEGS100000;// 无穷大intmain(intargc,char*argv[]){intdatasets0,cases0;cindatasets;coutSHIPPING ROUTES OUTPUTendlendl;while(datasets--){intM,N,P;cinMNP;// 仓库代码到索引的映射mapstring,intwarehouses;for(inti1;iM;i){string codes;cincodes;warehouses[codes]i;}// 初始化距离矩阵intlegs[M1][M1];for(inti1;iM;i){for(intj1;jM;j)legs[i][j]MAX_LEGS;legs[i][i]0;}// 读取边运输段for(inti1;iN;i){string start,next;cinstartnext;legs[warehouses[start]][warehouses[next]]1;legs[warehouses[next]][warehouses[start]]1;}// Floyd-Warshall 计算所有点对最短路径for(intk1;kM;k)for(inti1;iM;i)for(intj1;jM;j)if(legs[i][k]legs[k][j]legs[i][j])legs[i][j]legs[i][k]legs[k][j];coutDATA SET casesendlendl;// 处理查询for(inti1;iP;i){intsize;string start,next;cinsizestartnext;intdistlegs[warehouses[start]][warehouses[next]];if(distMAX_LEGS){coutNO SHIPMENT POSSIBLEendl;continue;}cout$size*dist*100endl;}coutendl;}coutEND OF OUTPUTendl;return0;}