結果

問題 No.1 道のショートカット
ユーザー vjudge1
提出日時 2025-09-04 21:30:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,070 bytes
コンパイル時間 960 ms
コンパイル使用メモリ 114,500 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-04 21:30:33
合計ジャッジ時間 2,851 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 3
other AC * 4 WA * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:23:39: warning: ‘V’ is used uninitialized [-Wuninitialized]
   23 |     auto input = make_unique<int[]>(4 * V);
      |                                     ~~^~~
main.cpp:19:15: note: ‘V’ was declared here
   19 |     int N, C, V;
      |               ^

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <memory>
using namespace std;

const int INF = 1e9;

struct Edge {
    int to, cost, time;
    Edge(int t, int c, int tm) : to(t), cost(c), time(tm) {}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, C, V;
    cin >> N >> C, V;
    
    // Use unique_ptr for automatic memory management with move semantics
    auto input = make_unique<int[]>(4 * V);
    for (int i = 0; i < 4 * V; i++) {
        cin >> input[i];
    }
    
    // Build graph with move semantics
    vector<vector<Edge>> graph(N);
    for (int i = 0; i < V; i++) {
        int s = input[i] - 1;
        int t = input[V + i] - 1;
        int cost = input[2 * V + i];
        int time = input[3 * V + i];
        graph[s].emplace_back(t, cost, time);
    }
    
    // Free input memory early
    input.reset();
    
    // Use 2D array with unique_ptr for DP table
    auto dp = make_unique<int[]>(N * (C + 1));
    fill_n(dp.get(), N * (C + 1), INF);
    dp[0 * (C + 1) + C] = 0;
    
    // Main DP loop with pointer arithmetic
    for (int i = 0; i < N; i++) {
        int* current_row = dp.get() + i * (C + 1);
        auto& edges = graph[i];
        
        for (int k = C; k >= 0; k--) {
            if (current_row[k] == INF) continue;
            
            for (const auto& edge : edges) {
                if (k >= edge.cost) {
                    int* target_row = dp.get() + edge.to * (C + 1);
                    int& target = target_row[k - edge.cost];
                    int new_time = current_row[k] + edge.time;
                    if (new_time < target) {
                        target = new_time;
                    }
                }
            }
        }
    }
    
    // Calculate result with move of the last row
    int* last_row = dp.get() + (N - 1) * (C + 1);
    int result = INF;
    for (int k = 0; k <= C; k++) {
        result = min(result, last_row[k]);
    }
    
    cout << (result == INF ? -1 : result) << endl;
    
    return 0;
}
0