题目描述题目要求规划一条kkk天的旅行路线每天从当前城市飞往另一个城市第kkk天结束时必须在城市nnn亚特兰大。每个航班的价格按周期变化周期长度ddd1≤d≤301 \le d \le 301≤d≤30价格为000表示当天无航班。求最小总花费若无解输出No flight possible.。输入格式输入包含多个场景。每个场景第一行两个整数nnn2≤n≤102 \le n \le 102≤n≤10和kkk1≤k≤10001 \le k \le 10001≤k≤1000。接下来n(n−1)n(n-1)n(n−1)行每行描述一对城市之间的航班价格。第111到n−1n-1n−1行是从城市111到2,3,…,n2,3,\ldots,n2,3,…,n的航班第nnn到2n−22n-22n−2行是从城市222到1,3,4,…,n1,3,4,\ldots,n1,3,4,…,n以此类推。每个航班描述以整数ddd开头后跟ddd个整数表示每天的价格。输入以nk0n k 0nk0结束。输出格式对于每个场景输出Scenario #X然后输出The best flight costs x.或No flight possible.每个场景后跟一个空行。样例输入3 6 2 130 150 3 75 0 80 7 120 110 0 100 110 120 0 4 60 70 60 50 3 0 135 140 2 70 80 2 3 2 0 70 1 80 0 0输出Scenario #1 The best flight costs 460. Scenario #2 No flight possible.题目分析本题的核心是动态规划。动态规划定义设cost[d][c]\textit{cost}[d][c]cost[d][c]表示第ddd天到达城市ccc的最小花费。初始cost[1][c]\textit{cost}[1][c] cost[1][c]航班价格若存在。转移cost[d][c]min⁡p≠c{cost[d−1][p]price(p→c,d)} \textit{cost}[d][c] \min_{p \ne c} \{ \textit{cost}[d-1][p] \text{price}(p \to c, d) \}cost[d][c]pcmin​{cost[d−1][p]price(p→c,d)}其中price(p→c,d)\textit{price}(p \to c, d)price(p→c,d)为第ddd天从ppp到ccc的航班价格若为000则不可用。复杂度分析k≤1000k \le 1000k≤1000n≤10n \le 10n≤10时间复杂度O(k×n2)O(k \times n^2)O(k×n2)。代码实现// Always on the Run// UVa ID: 590// Verdict: Accepted// Submission Date: 2016-09-26// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);vectorvectorintschedule[12];intcost[1100][12];intn,k,cases0;while(cinnk,n){for(inti1;in;i)schedule[i].clear();inttotaln*(n-1),count;for(inti1;in;i){schedule[i].push_back(vectorint(1,0));for(intj1;jn;j){if(ij){schedule[i].push_back(vectorint(1,0));continue;}cincount;vectorintlines(count);for(intl0;lcount;l)cinlines[l];schedule[i].push_back(lines);}}memset(cost,0,sizeof(cost));for(inti1;in;i)cost[1][i]schedule[1][i][0];for(inti2;ik;i){for(intj1;jn;j){for(intl1;ln;l){if(lj)continue;intfeeschedule[j][l][(i-1)%schedule[j][l].size()];if(fee0||cost[i-1][j]0)continue;if(cost[i][l]0)cost[i][l]cost[i-1][j]fee;elsecost[i][l]min(cost[i][l],cost[i-1][j]fee);}}}coutScenario #cases\n;if(cost[k][n]0)coutThe best flight costs cost[k][n].\n\n;elsecoutNo flight possible.\n\n;}return0;}