UVa 590 Always on the Run

2026/6/26 0:18:00

题目描述

题目要求规划一条kkk天的旅行路线，每天从当前城市飞往另一个城市，第kkk天结束时必须在城市nnn（亚特兰大）。每个航班的价格按周期变化（周期长度ddd，1≤d≤301 \le d \le 301≤d≤30），价格为000表示当天无航班。求最小总花费，若无解输出No flight possible.。

输入格式

输入包含多个场景。每个场景第一行两个整数nnn（2≤n≤102 \le n \le 102≤n≤10）和kkk（1≤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个整数表示每天的价格。输入以n=k=0n = k = 0n=k=0结束。

输出格式

对于每个场景，输出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≤1000，n≤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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);vector<vector<int>>schedule[12];intcost[1100][12];intn,k,cases=0;while(cin>>n>>k,n){for(inti=1;i<=n;i++)schedule[i].clear();inttotal=n*(n-1),count;for(inti=1;i<=n;i++){schedule[i].push_back(vector<int>(1,0));for(intj=1;j<=n;j++){if(i==j){schedule[i].push_back(vector<int>(1,0));continue;}cin>>count;vector<int>lines(count);for(intl=0;l<count;l++)cin>>lines[l];schedule[i].push_back(lines);}}memset(cost,0,sizeof(cost));for(inti=1;i<=n;i++)cost[1][i]=schedule[1][i][0];for(inti=2;i<=k;i++){for(intj=1;j<=n;j++){for(intl=1;l<=n;l++){if(l==j)continue;intfee=schedule[j][l][(i-1)%schedule[j][l].size()];if(fee==0||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);}}}cout<<"Scenario #"<<++cases<<'\n';if(cost[k][n]>0)cout<<"The best flight costs "<<cost[k][n]<<".\n\n";elsecout<<"No flight possible.\n\n";}return0;}