Uva 590 Always on the run （Dp） - c++编程基础

标城市是城市 n。

给你 n , k 的值。然后有 n*(n-1) 行，第 i 个（n-1 ）行表示城市 i 到其它

城市的飞机的时间点的价格。

例如 3 75 0 80 表示第一天价格是 75 ，第二天没有航班，第三天价格是 80

第四天价格是 75 ，第五天没有航班，第六天价格是 80

......

题目问你那个游玩的人能否在第 k 天到达城市 n ，如果能，输出最小的花

费，否则输出 “ No flight possible.”

思路 : dp[ i ][ j ] 表示第 i 天到达城市 j 的最小的花费。dp[ i ][ j ] 初始化为 -1 。

即当 j 城市在第 i 天能到达城市k 的话 (假设花费为cost，前提dp[ i-1 ][ j ] != -1) ：

if(dp[ i ] [ k ] == -1 ) dp[ i ][ k ]=dp[ i-1 ][ j ]+cost;
else dp[ i ][ k ]=min(dp[ i ][ k ],dp[ i-1 ][ j ]+cost);

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int N=1010; const int M=15; int dp[N][M],n,m,cnt; vector 
      
        a[M][M]; void initial() { memset(dp,-1,sizeof(dp)); for(int i=0; i

Uva 590 Always on the run （Dp）(二)