結果

問題 No.1 道のショートカット
コンテスト
ユーザー ooaiu
提出日時 2025-08-18 12:30:14
言語 cLay
(20241019-1)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 553 bytes
コンパイル時間 2,995 ms
コンパイル使用メモリ 194,488 KB
実行使用メモリ 7,756 KB
最終ジャッジ日時 2025-08-18 12:30:20
合計ジャッジ時間 4,970 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:355:9: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  355 |     auto[e,v,c]=hq.pop();
      |         ^
main.cpp:359:13: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  359 |     for(auto[u,y,m]:G[v]){
      |             ^

ソースコード

diff # 

ll@(N,C,V),@(S--)[V],@(T--)[V],@Y[V],@M[V];
vector<vector<array<ll,3>>>G(N);
rep(i,V)G[S[i]].push_back({T[i], Y[i], M[i]});
Heap<array<ll,3>>hq;hq.walloc(2<<17);
ll dp[N][C+1];rep(i,N)rep(j,C+1)dp[i][j]=1d18;
dp[0][C]=0;
hq.push({0,0,C});
while(hq.size) {
    auto[e,v,c]=hq.pop();
    if(dp[v][c]!=e)continue;
    for(auto[u,y,m]:G[v]){
        ll nc=c-y;
        if(nc>=0&&dp[u][nc]>dp[v][c]+m){
            dp[u][nc]=dp[v][c]+m;
            hq.push({dp[u][nc],u,nc});
        }
    }
}
ll ans = 1d18;
rep(i,C+1)ans<?=dp[N-1][i];
wt(ans==1d18?-1:ans);
0