UVa-590 : Always on the run
問題概要
都市がN(<10)個ある。各都市間を飛行機が結んでいて、コストは日によって周期的に変わる。毎日必ず飛行機を利用して、ちょうどK(<1000)日後に指定された都市にいるようにしたい。必要な最小費用を求める問題。無理な時はその旨出力する。
解法
(i日目、どの都市にいるか)を状態のキーにしてDPするだけ。
acceptされたコード
計算量O(N^2 * K)。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10; const int MAX_K = 1000; const int MAX_D = 30; const int INF = 1<<29; int N, K; int dp[MAX_K + 1][MAX_N]; int term[MAX_N][MAX_N]; int cost[MAX_N][MAX_N][MAX_D]; bool init(){ scanf("%d%d", &N, &K); if(N==0 && K==0){ return false; } for(int i=0; i<N; i++){ for(int j=0; j<N; j++)if(i!=j){ scanf("%d", term[i] + j); for(int k=0; k<term[i][j]; k++){ scanf("%d", cost[i][j] + k); } } } return true; } int solve(){ for(int i=0; i<=K; i++){ fill(dp[i], dp[i] + MAX_N, INF); } dp[0][0] = 0; for(int i=0; i<K; i++){ for(int j=0; j<N; j++){ for(int k=0; k<N; k++)if(j != k && cost[j][k][i%term[j][k]]){ dp[i+1][k] = min(dp[i+1][k], dp[i][j] + cost[j][k][i%term[j][k]]); } } } return dp[K][N-1] == INF ? -1 : dp[K][N-1]; } int main(){ for(int c=1; init(); c++){ printf("Scenario #%d\n", c); int ans = solve(); if(ans == -1){ puts("No flight possible."); } else{ printf("The best flight costs %d.\n", ans); } puts(""); } return 0; }