結果
問題 | No.1 道のショートカット |
ユーザー |
👑 |
提出日時 | 2022-09-10 16:12:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 1,311 bytes |
コンパイル時間 | 1,066 ms |
コンパイル使用メモリ | 85,400 KB |
最終ジャッジ日時 | 2025-02-07 03:53:07 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <vector> #include <queue> using namespace std; struct d{ int s,t,y,m; }; struct dd{ int t,y,m; }; struct k{ int p,c,t; bool operator<(const k a) const { if(t == a.t){ if(c == a.c){ return p < a.p; } return c < a.c; } return t < a.t; } }; int main(){ int n,c,v;cin>>n>>c>>v; vector<vector<int>> Z(n,vector<int>(c+1,1000000)); vector<d> A(v); vector<dd> B[n]; for(int i = 0; v > i; i++){ cin>>A[i].s;A[i].s--; } for(int i = 0; v > i; i++){ cin>>A[i].t;A[i].t--; } for(int i = 0; v > i; i++){ cin>>A[i].y; } for(int i = 0; v > i; i++){ cin>>A[i].m; } for(int i = 0; v > i; i++){ B[A[i].s].push_back({A[i].t,A[i].y,A[i].m}); } //dijkstra priority_queue<k> X; X.push({0,c,0}); Z[0][c] = 0; while(X.size()){ auto x = X.top();X.pop(); for(int i = 0; B[x.p].size() > i; i++){ if(B[x.p][i].y > x.c)continue; if(Z[B[x.p][i].t][x.c-B[x.p][i].y] > Z[x.p][x.c]+B[x.p][i].m){ Z[B[x.p][i].t][x.c-B[x.p][i].y] = Z[x.p][x.c]+B[x.p][i].m; X.push({B[x.p][i].t,x.c-B[x.p][i].y,Z[x.p][x.c]+B[x.p][i].m}); } } } int ans = Z[n-1][0]; for(int i = 0; c >= i; i++){ ans = min(ans,Z[n-1][i]); } cout << (ans==1000000?-1:ans) << endl; }