CFR 721 C. Journey ( DP )

Problem - C - Codeforces
題意：
給一個有向無環圖，保證 1 到 N 連通，有邊權。求不超過給定 T 的總邊權下，由 1 移動到 N 最多可以經過多少不同節點，以及其路徑。
解法：
dp[ i ][ j ] : 最後在 i 號節點，已拜訪 j 個節點。
因為拜訪過的節點不可能再被拜訪( 無環 )，因此可以這樣做。
注意記憶體常數上很容易爆炸。

int N, M, T;
vvp G;

void init(){
    cin >> N >> M >> T;
    G = vvp( N );
    for( int i = 0; i < M; ++i ){
        int u, v, w; cin >> u >> v >> w;
        G[ u - 1 ].push_back( pii( w, v - 1 ) );
    }
}

vvi dp;
vvi pre;

void preprocess(){
    dp = vvi( N, vi( N + 1, INF ) );
    pre = vvi( N, vi( N + 1, -1 ) );
    dp[ 0 ][ 1 ] = 0;
    for( int i = 1; i < N; ++i )
        for( int j = 0; j < N; ++j )
            for( int k = 0; k < G[ j ].size(); ++k )
                if( upmin( dp[ G[ j ][ k ].second ][ i + 1 ], dp[ j ][ i ] + G[ j ][ k ].first ) )
                    pre[ G[ j ][ k ].second ][ i + 1 ] = j;
}

void solve(){
    for( int i = N; ; --i ){
        assert( i > 0 );
        if( dp[ N - 1 ][ i ] <= T ){
            dp.clear();
            cout << i << endl;
            stack< int > route;
            for( int u = N - 1, f = i; u != -1; u = pre[ u ][ f-- ] )
                route.push( u );
            for( ; not route.empty(); route.pop() )
                cout << route.top() + 1 << " \n"[ ( int ) route.size() == 1 ];
            return;
        }
    }
}