UVa 523 Minimum Transport Cost

题目描述题目要求在有NNN个城市的有向图中计算从源城市到目标城市的最小运输费用。费用由两部分组成路径上的运输成本边权。经过中间城市时需要缴纳的税费源城市和目标城市不纳税。给定邻接矩阵aij−1a_{ij} -1aij​−1表示无直接路径和每个城市的税费以及多个查询源城市和目标城市输出每条路径的节点序列和总费用。输入格式第一行一个整数MMM表示数据集的个数后面跟一个空行。每个数据集包含NNN行每行NNN个整数表示邻接矩阵。一行NNN个整数表示每个城市的税费。多行每行两个整数ccc和ddd表示查询。输入以空行结束。两个连续数据集之间由一个空行分隔。输出格式对于每个查询输出From c to d : Path: c - ... - d Total cost : ...若cdc dcd路径直接输出c - d。不同查询的输出之间无空行。不同数据集的输出之间由一个空行分隔。样例输入1 0 3 22 -1 4 3 0 5 -1 -1 22 5 0 9 20 -1 -1 9 0 4 4 -1 20 4 0 5 17 8 3 1 1 3 3 5 2 4输出From 1 to 3 : Path: 1-3 Total cost : 21 From 3 to 5 : Path: 3-5 Total cost : 16 From 2 to 4 : Path: 2-4 Total cost : 17题目分析本题的核心是计算经过中间节点时需加税费的最短路径。可以使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法的变体。状态定义设cost[i][j]cost[i][j]cost[i][j]为从城市iii到城市jjj的最短总费用包含中间节点的税费。初始化若iji jijcost[i][j]0cost[i][j] 0cost[i][j]0。若存在直接边i→ji \to ji→jcost[i][j]aijcost[i][j] a_{ij}cost[i][j]aij​。否则cost[i][j]∞cost[i][j] \inftycost[i][j]∞。转移方程在 Floyd-Warshall 算法中考虑经过中间节点kkk的路径cost[i][j]min⁡(cost[i][j], cost[i][k]cost[k][j]tax[k]) cost[i][j] \min(cost[i][j], \; cost[i][k] cost[k][j] tax[k])cost[i][j]min(cost[i][j],cost[i][k]cost[k][j]tax[k])注意中间节点kkk的税费只加一次。路径记录使用path[i][j]path[i][j]path[i][j]记录从iii到jjj的最短路径中iii的下一个节点或中间节点。在更新时若通过kkk的路径更优则设置path[i][j]kpath[i][j] kpath[i][j]k。输出时递归打印路径。复杂度分析Floyd-Warshall\texttt{Floyd-Warshall}Floyd-WarshallO(N3)O(N^3)O(N3)N≤100N \le 100N≤100可接受。代码实现// Minimum Transport Cost// UVa ID: 523// Verdict: Accepted// Submission Date: 2016-08-18// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intcost[100][100],path[100][100],tax[100],cities;voidfindPath(intfrom,intto){if(path[from][to]0){intkpath[from][to];findPath(from,k);cout--k;findPath(k,to);}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcasesstoi(line);getline(cin,line);for(intc1;ccases;c){if(c1)cout\n;getline(cin,line);istringstreamiss(line);intvalue;cities0;while(issvalue)cost[1][cities]value;for(inti2;icities;i){getline(cin,line);iss.clear();iss.str(line);intcounter0;while(issvalue)cost[i][counter]value;}getline(cin,line);iss.clear();iss.str(line);intcounter1;while(issvalue)tax[counter]value;memset(path,0,sizeof(path));for(intk1;kcities;k)for(inti1;icities;i)for(intj1;jcities;j)if(cost[i][k]0cost[k][j]0(cost[i][j]-1||cost[i][k]cost[k][j]tax[k]cost[i][j])){cost[i][j]cost[i][k]cost[k][j]tax[k];path[i][j]k;}boolfirst_linetrue;while(getline(cin,line),line.length()0){if(first_line)first_linefalse;elsecout\n;intfrom,to;iss.clear();iss.str(line);issfromto;coutFrom from to to :\n;coutPath: from;findPath(from,to);if(from!to)cout--to;cout\n;coutTotal cost : cost[from][to]\n;}}return0;}