結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2022-03-08 09:27:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 5,000 ms |
コード長 | 1,549 bytes |
コンパイル時間 | 4,496 ms |
コンパイル使用メモリ | 261,672 KB |
最終ジャッジ日時 | 2025-01-28 07:43:44 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using ll = long long; int n,c,v; using TUP = tuple<int,int,int>; vector<int> S,T,Y,M; vector<vector<TUP>> G; int cost[50][301]; const int INF = INT_MAX/2; void solve(){ for(int i = 0;i<50;i++){ for(int j = 0;j<301;j++){ cost[i][j] = INF; } } cost[0][0] = 0; priority_queue<TUP,vector<TUP>,greater<>> PQ; PQ.emplace(0,0,0); while(PQ.size()){ auto [fromTime,from,fromMon] = PQ.top(); PQ.pop(); if(cost[from][fromMon]!=fromTime)continue; for(auto [to,toMon,toTime]:G[from]){ //cout<<G[from].size()<<' '<<from<<' '<<to<<endl; int nxMon = fromMon + toMon; if(nxMon>300)continue; int nxTime = fromTime + toTime; if(cost[to][nxMon]>nxTime){ cost[to][nxMon]=nxTime; PQ.emplace(nxTime,to,nxMon); } //cout<<from<<endl; } } int ans = INF; for(int i = 0;i <= c;i++){ ans = min(cost[n-1][i],ans); } if(ans == INF)ans = -1; cout<<ans<<endl; /* for(int i = 0;i<50;i++){ for(int j = 0;j<301;j++){ if(cost[i][j]!=INF){ cout<<i<<' '<<j<<' '<<cost[i][j]<<endl; } } } cout<<cost[1][10]<<endl; cout<<cost[2][10]<<endl; */ } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> c >> v; S = T = Y = M = vector<int>(v); for(int i = 0;i<v;i++)cin >> S[i]; for(int i = 0;i<v;i++)cin >> T[i]; for(int i = 0;i<v;i++)cin >> Y[i]; for(int i = 0;i<v;i++)cin >> M[i]; G.resize(n); for(int i = 0;i<v;i++){ G[S[i]-1].push_back(TUP(T[i]-1,Y[i],M[i])); } solve(); }