题目描述随着新型Thrust Zoom\texttt{Thrust Zoom}Thrust Zoom超空间驱动器的引入Hyper Commodities\texttt{Hyper Commodities}Hyper Commodities一家新泽西州的进出口企业集团开始与宇宙中最遥远的星系进行贸易。Hyper Commodities\texttt{Hyper Commodities}Hyper Commodities希望从Plural Z\texttt{Plural Z}Plural Z星系的某些星系进口商品。已知事实每个星系包含111到262626颗行星每颗行星用一个字母A∼ZA \sim ZA∼Z标识每颗行星专门生产和出口一种商品同一星系内不同行星出口不同商品某些行星之间有超空间航线相连可以自由贸易如果两颗行星通过中间行星间接相连每经过一个中间行星中间行星会收取5%5\%5%的运输费即货物只留下95%95\%95%每个星系至少有一颗行星愿意开设通往地球的Thrust Zoom\texttt{Thrust Zoom}Thrust Zoom航线每颗行星的出口商品有一个相对价值小于101010的正实数问题考虑运输费用后哪颗行星的出口价值最高输入格式每个星系描述以整数NNN开头行星数量。接下来NNN行每行包含行星的字母标识空格出口的相对价值格式d.dd空格一个字符串包含字母和/或*字母表示到该行星的航线*表示愿意开通到地球的Thrust Zoom\texttt{Thrust Zoom}Thrust Zoom航线输出格式对于每个星系输出一行Import from X其中XXX是价值最高的行星字母。样例输入1 F 0.81 * 5 E 0.01 *A D 0.01 A* C 0.01 *A A 1.00 EDCB B 0.01 A* 10 S 2.23 Q* A 9.76 C K 5.88 MI E 7.54 GC M 5.01 OK G 7.43 IE I 6.09 KG C 8.42 EA O 4.55 QM Q 3.21 SO样例输出Import from F Import from A Import from A题目分析问题的本质这是一个带权最短路径问题。地球可以视为一个特殊节点与愿意开通Thrust Zoom\texttt{Thrust Zoom}Thrust Zoom航线的行星直接相连。从地球到某行星的路径上每经过一个中间行星货物价值损失5%5\%5%。需要找出经过损失后价值最高的行星。数学模型将地球视为节点262626或000但代码中使用262626每颗行星为一个节点0∼250 \sim 250∼25航线是无向边从地球到行星iii的路径长度为dist[i]dist[i]dist[i]经过的边数地球直接连接的行星dist1dist 1dist1最终价值 原始价值×0.95dist−1\times 0.95^{dist-1}×0.95dist−1因为第一个节点是地球不需要收费需要仔细分析注意运输费由中间行星收取。如果地球直接与行星KKK相连则没有中间行星货物价值不变。如果经过ddd段航线则有d−1d-1d−1个中间行星每个收取5%5\%5%因此最终价值 原始价值×0.95d−1\times 0.95^{d-1}×0.95d−1。算法使用Dijkstra\texttt{Dijkstra}Dijkstra或BFS\texttt{BFS}BFS计算从地球到所有行星的最短路径边权均为111然后计算每个行星的最终价值取最大值。参考代码// Galactic Import// UVa ID: 388// Verdict: Accepted// Submission Date: 2016-07-04// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structedge{intto,weight;booloperator(constedgeanother)const{returnweightanother.weight;}};intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn;while(cinn){vectorvectorintedges(30);// 邻接表26 表示地球vectordoublevalue(30);// 行星原始价值charplanet;string line;for(inti1;in;i){cinplanet;cinvalue[planet-A];cinline;// 添加边for(charletter:line)if(letter*){edges[planet-A].push_back(26);edges[26].push_back(planet-A);}else{edges[planet-A].push_back(letter-A);edges[letter-A].push_back(planet-A);}}// Dijkstra 求最短路径边权为 1vectorintdistances(30,100000);distances[26]0;priority_queueedgeunvisited;unvisited.push((edge){26,0});while(!unvisited.empty()){edge vunvisited.top();unvisited.pop();for(autoe:edges[v.to])if(distances[v.to]1distances[e]){distances[e]distances[v.to]1;unvisited.push((edge){e,distances[e]});}}// 计算最终价值并找出最大值doublemaxValue-1.0;intimport_from-1;for(inti0;i25;i)if(distances[i]100000){// 经过 distances[i] 段航线有 distances[i]-1 个中间行星doublefinalValuevalue[i]*pow(0.95,distances[i]-1);if(finalValuemaxValue){maxValuefinalValue;import_fromi;}}coutImport from (char)(Aimport_from)endl;}return0;}