結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2019-10-17 15:57:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 896 bytes |
コンパイル時間 | 2,532 ms |
コンパイル使用メモリ | 179,164 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:42:17 |
合計ジャッジ時間 | 2,792 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include<bits/stdc++.h> #define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i) #define rep(i,a,b) for(int i=int(a);i<int(b);++i) #define All(x) (x).begin(),(x).end() using namespace std; typedef long long ll; int main(){ const int inf=1<<25; int N,C,V;cin>>N>>C>>V; vector<vector<int>> E(V,vector<int>(4)),dp(N+1,vector<int>(C+1,inf)); REP(i,4) REP(j,V) cin>>E[j][i]; vector<vector<tuple<int,int,int>>> to(N); REP(i,V){ int s=E[i][0]-1,t=E[i][1]-1,y=E[i][2],m=E[i][3]; to[s].push_back(tie(t,y,m)); } dp[0][C]=0; REP(u,N){ REP(i,to[u].size()){ int v,y,m; tie(v,y,m)=to[u][i]; REP(j,C+1){ if(j+y<=C) dp[v][j]=min(dp[v][j],dp[u][j+y]+m); } } } int ans=inf; REP(i,C+1) ans=min(ans,dp[N-1][i]); if(ans==inf) cout<<-1<<endl; else cout<<ans<<endl; }