Atomic Car Race

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem F

[解説]

DAG (Directed Acyclic Graph)上の最短経路問題。動的計画法
詳細は後日書きたいと思います。

[サンプルプログラム]

001 #include<iostream>
002 #include<stdio.h>
003 #include<cfloat>
004 #include<algorithm>
005 using namespace std;
006 #define MAX 100
007 #define DMAX 10000
008 
009 int D[MAX+1];
010 double T[DMAX+1];
011 double C[MAX+1];
012 int n, r;
013 double b, v, e, f;
014 
015 double getCost( int x ){
016     if ( x >= r ) return 1/(v - e*(x - r));
017     else return 1/(v - f*(r - x));
018 }
019 
020 void compute(){
021     T[0] = 0.0;
022     for ( int x = 1; x <= D[n]; x++ ){
023         T[x] = T[x-1] + getCost(x - 1);
024     }
025     
026     for ( int i = 1; i <= n; i++ ) C[i] = FLT_MAX;
027     C[0] = 0.0;
028     for ( int i = 1; i <= n; i++ ){
029         for ( int j = 0; j < i; j++ ){
030             C[i] = min( C[i], C[j] + T[D[i] - D[j]] + (j == 0 ? 0 : b) );
031         }
032     }
033     printf("%.4lf\n", C[n]);
034 }
035 
036 bool input(){
037     cin >> n;
038     if ( n == 0 ) return false;
039     D[0] = 0;
040     for ( int i = 1; i <= n; i++ ) cin >> D[i];
041     cin >> b >> r >> v >> e >> f;
042     return true;
043 }
044 
045 main(){
046     while ( input() ) compute();
047 }