結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

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

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

int shortestPath(int N, int C, vector<vector<Edge>>& graph) {
    vector<vector<int>> dp(N + 1, vector<int>(C + 1, numeric_limits<int>::max()));
    priority_queue<State, vector<State>, greater<State>> pq;

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

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

        if (curr.node == N) return curr.time;  // Found shortest path to town N

        if (curr.time > dp[curr.node][curr.cost]) continue;

        for (Edge& e : graph[curr.node]) {
            int newCost = curr.cost + e.cost;
            int newTime = curr.time + e.time;

            if (newCost <= C && newTime < dp[e.to][newCost]) {
                dp[e.to][newCost] = newTime;
                pq.push({e.to, newCost, newTime});
            }
        }
    }
    return -1;  // No valid path within budget
}

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

    vector<vector<Edge>> graph(N + 1);

    for (int i = 0; i < M; i++) {
        int a, b, y, t;
        cin >> a >> b >> y >> t;
        graph[a].push_back({b, y, t});
        graph[b].push_back({a, y, t});  // Assuming bidirectional roads
    }

    cout << shortestPath(N, C, graph) << endl;
    return 0;
}
0