結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// Struct to represent an edge with named fields
struct Edge {
    int target_node;
    int cost;
    int time;
    
    Edge(int t, int c, int tm) : target_node(t), cost(c), time(tm) {}
};

int main() {
    // Read number of nodes, budget, and number of edges
    int num_nodes, budget, num_edges;
    cin >> num_nodes >> budget >> num_edges;
    
    // Arrays to store edge information
    vector<int> source_nodes(num_edges);
    vector<int> target_nodes(num_edges);
    vector<int> edge_costs(num_edges);
    vector<int> edge_times(num_edges);
    
    // Read source nodes (convert to 0-based indexing)
    for (int i = 0; i < num_edges; i++) {
        cin >> source_nodes[i];
        source_nodes[i]--;
    }
    
    // Read target nodes (convert to 0-based indexing)
    for (int i = 0; i < num_edges; i++) {
        cin >> target_nodes[i];
        target_nodes[i]--;
    }
    
    // Read edge costs
    for (int i = 0; i < num_edges; i++) {
        cin >> edge_costs[i];
    }
    
    // Read edge times
    for (int i = 0; i < num_edges; i++) {
        cin >> edge_times[i];
    }
    
    // Create adjacency list for the graph using Edge struct
    vector<vector<Edge>> graph(num_nodes);
    for (int i = 0; i < num_edges; i++) {
        int source = source_nodes[i];
        int target = target_nodes[i];
        int cost = edge_costs[i];
        int time = edge_times[i];
        graph[source].push_back(Edge(target, cost, time));
    }
    
    // Initialize DP table
    // dp[node][remaining_budget] = minimum time to reach node with remaining_budget
    const int INFINITY_VALUE = 1000000000;
    vector<vector<int>> dp(num_nodes, vector<int>(budget + 1, INFINITY_VALUE));
    
    // Start at node 0 with full budget, time = 0
    dp[0][budget] = 0;
    
    // Dynamic programming: for each node, process all possible budget states
    for (int current_node = 0; current_node < num_nodes; current_node++) {
        for (int remaining_budget = budget; remaining_budget >= 0; remaining_budget--) {
            
            // Skip if this state is unreachable
            if (dp[current_node][remaining_budget] == INFINITY_VALUE) {
                continue;
            }
            
            // Process all outgoing edges from current node
            for (const Edge& edge : graph[current_node]) {
                // Check if we have enough budget to take this edge
                if (remaining_budget >= edge.cost) {
                    int new_budget = remaining_budget - edge.cost;
                    int new_time = dp[current_node][remaining_budget] + edge.time;
                    
                    // Update if we found a better path
                    if (new_time < dp[edge.target_node][new_budget]) {
                        dp[edge.target_node][new_budget] = new_time;
                    }
                }
            }
        }
    }
    
    // Find the minimum time to reach the last node (node n-1)
    int min_time = INFINITY_VALUE;
    for (int remaining_budget = 0; remaining_budget <= budget; remaining_budget++) {
        min_time = min(min_time, dp[num_nodes - 1][remaining_budget]);
    }
    
    // Output result
    if (min_time == INFINITY_VALUE) {
        cout << -1 << endl;
    } else {
        cout << min_time << endl;
    }
    
    return 0;
}
0