結果

問題 No.1 道のショートカット
ユーザー vjudge1
提出日時 2025-06-01 19:33:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,666 bytes
コンパイル時間 4,232 ms
コンパイル使用メモリ 288,320 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-01 19:33:51
合計ジャッジ時間 4,397 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

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

struct State {
    int node, used_cost, total_time;
    bool operator>(const State &other) const { return total_time > other.total_time; }
};

int shortestPath(int n, int c, vector<vector<Edge>>& graph) {
    vector<vector<int>> dp(n, vector<int>(c+1, INT_MAX)); // DP table: min time to reach each node with a cost
    priority_queue<State, vector<State>, greater<State>> pq;

    dp[0][0] = 0;
    pq.push({0, 0, 0});

    while (!pq.empty()) {
        State curr = pq.top();
        pq.pop();

        if (curr.total_time > dp[curr.node][curr.used_cost]) continue;

        for (auto [to, cost, time] : graph[curr.node]) {
            int new_cost = curr.used_cost + cost;
            int new_time = curr.total_time + time;

            if (new_cost <= c && new_time < dp[to][new_cost]) {
                dp[to][new_cost] = new_time;
                pq.push({to, new_cost, new_time});
            }
        }
    }

    int ans = INT_MAX;
    for (int i = 0; i <= c; i++) ans = min(ans, dp[n-1][i]);
    
    return (ans == INT_MAX ? -1 : ans);
}

int main() {
    int n, c, v;
    cin >> n >> c >> v;

    vector<vector<Edge>> graph(n);
    vector<int> s(v), t(v), y(v), m(v);

    for (int i = 0; i < v; i++) cin >> s[i];
    for (int i = 0; i < v; i++) cin >> t[i];
    for (int i = 0; i < v; i++) cin >> y[i];
    for (int i = 0; i < v; i++) cin >> m[i];

    for (int i = 0; i < v; i++) {
        s[i]--, t[i]--;  // Convert to zero-based indexing
        graph[s[i]].push_back({t[i], y[i], m[i]});
    }

    cout << shortestPath(n, c, graph) << endl;
    return 0;
}
0