読者です 読者をやめる 読者になる 読者になる

yukicoder ★★★ No.1 道のショートカット

おみくじで記念すべき1を引きました。

問題

No.1 道のショートカット - yukicoder

考察

グラフ、に見せかけて、パスは番号が増加するものしかないためDPできます。
お金、時間の2つのパラメーターがあるため、1つはDP表に入れてしまえば答えを求めることができます。

この場合、お金は初期値から増やす必要が無いため、こちらをDP表に入れます。
番号1からNまで、お金を網羅的に見て遷移をしてゆけば、最終的に番号Nの所で最短の時間を探せばそれが答えです。

入力の形式が若干厄介なので注意。

コード

struct Edge {
    int to, cost, time;
};

int main() {
    int N, C, V;
    cin >> N >> C >> V;

    vector< vector<Edge> > graph(N);
    {
        vi s(V), t(V), y(V), m(V);
        rep(i, V) cin >> s[i];
        rep(i, V) cin >> t[i];
        rep(i, V) cin >> y[i];
        rep(i, V) cin >> m[i];

        rep(i, V) {
            graph[s[i]-1].push_back(Edge{t[i]-1, y[i], m[i]});
        }
    }

    vvi dp(N, vi(C+10, INF));
    dp[0][C] = 0;
    rep(i, N) {
        rep(j, C+1) {
            if(dp[i][j] == INF)
                continue;

            tr(it, graph[i]) {
                if(j - it->cost >= 0)
                    chmin(dp[it->to][j - it->cost], dp[i][j] + it->time);
            }
        }
    }

    int ans = INF;
    rep(i, C+1)
        chmin(ans, dp[N-1][i]);

    if(ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;
    
    return 0;
}

備考

1番というだけあってシンプルな問題。
解くとなんだかスッキリしました。