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;
}