AOJ 2151 Brave Princess Revisited
AOJ 2151 Brave Princess Revisited
解法
宿と予算が少ない！ ということで動的計画法で解こうとしました
（トポロジカルソートできていないのでDPじゃない）。
設計メモ
dp[現在地][残りの予算] : 最小化された盗賊らの人数
d[出発地][到着地] = 出発地と到着地の距離（コスト）
e[出発地][到着地] = 出発地と到着地の間に出てくる盗賊らの人数
dp = INF
for( n 回 )
for( i : 出発地 )
for( j : 到着地 )
for( k : 出発地時点の予算 )
if 予算が足りる
// 予算を使う
dp[j][ k - d[i][j] ] = min( dp[j][ k - d[i][j] ], dp[i][ k ] )
end
// 予算を使わない
dp[j][ k ] = min( dp[j][ k ], dp[i][ k ] + e[i][j] )一番最初は、番号が戻ってくること（サンプルの最後）を忘れていて
書き直さなきゃ〜と思ったのですが、一番多く戻るパターンでも
n - 3回しかないことに気付けて、ひどい方法ですがその分
ループさせてます（やっぱり怖いのでn回回しています...）。
で最大
くらいなので大丈夫そう。
こんな感じで、あとは欲しい処理、変数を足していきます。
ソースコード
import java.util.Arrays; import java.util.Scanner; public class Main { Scanner sc; void run() { for ( ;; ) { int n = ni(); int m = ni(); int l = ni(); if ( ( n | m | l ) == 0 ) { break; } int[][] dm = new int[n + 1][n + 1]; int[][] em = new int[n + 1][n + 1]; boolean[][] lk = new boolean[n + 1][n + 1]; for ( int i = 0; i < m; ++i ) { int a = ni(); int b = ni(); int d = ni(); int e = ni(); dm[ a ][ b ] = dm[ b ][ a ] = d; em[ a ][ b ] = em[ b ][ a ] = e; lk[ a ][ b ] = lk[ b ][ a ] = true; } boolean[][] ok = new boolean[n + 1][l + 1]; int[][] dp = new int[n + 1][l + 1]; for ( int[] v : dp ) Arrays.fill( v, 1 << 28 ); dp[ 1 ][ l ] = 0; ok[ 1 ][ l ] = true; for ( int h = 0; h < n; ++h ) { for ( int i = 1; i <= n; ++i ) { for ( int j = 1; j <= n; ++j ) { if ( lk[ i ][ j ] ) { for ( int k = 0; k <= l; ++k ) { if ( ok[ i ][ k ] ) { if ( k - dm[ i ][ j ] >= 0 ) { dp[ j ][ k - dm[ i ][ j ] ] = Math.min( dp[ j ][ k - dm[ i ][ j ] ], dp[ i ][ k ] ); ok[ j ][ k - dm[ i ][ j ] ] = true; // debug( i, j, k - dm[ i ][ j ], dp[ j ][ k - dm[ i ][ j ] ] ); } dp[ j ][ k ] = Math.min( dp[ j ][ k ], dp[ i ][ k ] + em[ i ][ j ] ); ok[ j ][ k ] = true; // debug( "a", i, j, k, dp[ j ][ k ] ); } } } } } } int min = 1 << 28; for ( int k = 0; k <= l; ++k ) { min = Math.min( min, dp[ n ][ k ] ); } System.out.println( min ); } } Main() { sc = new Scanner( System.in ); } int ni() { return sc.nextInt(); } public static void main(String[] args) { new Main().run(); } void debug(Object... os) { System.err.println( Arrays.deepToString( os ) ); } }
