結果
問題 | No.1545 [Cherry 2nd Tune N] Anthem |
ユーザー |
![]() |
提出日時 | 2024-10-06 23:47:54 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 183 ms / 3,000 ms |
コード長 | 1,831 bytes |
コンパイル時間 | 1,583 ms |
コンパイル使用メモリ | 122,372 KB |
実行使用メモリ | 43,008 KB |
最終ジャッジ日時 | 2024-10-06 23:48:09 |
合計ジャッジ時間 | 13,079 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 67 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; using ll = long long; #include<queue> int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll n,s,t,k; cin>>n>>s>>t>>k; s--;t--; vector<ll> x(n); for(int i = 0;i<n;i++) cin>>x[i]; vector<vector<pair<ll,ll>>> g(n); int m; cin>>m; for(int i = 0;i<m;i++){ ll a,b,y; cin>>a>>b>>y; a--;b--; g[a].push_back(make_pair(b,y)); } vector<vector<ll>> dp(n,vector<ll>(k+1,1e18)); vector<vector<pair<ll,ll>>> prev(n,vector<pair<ll,ll>>(k+1,make_pair(-1,-1))); dp[s][1] = x[s]; using dat = pair<ll,pair<ll,ll>>; priority_queue<dat,vector<dat>,greater<dat>> que; que.push({x[s],{s,1}}); while(que.size()){ auto now = que.top(); que.pop(); int ni = now.second.first; int t = now.second.second; if(dp[ni][t]!=now.first) continue; for(auto itr:g[ni]){ int to = itr.first; ll cost = now.first + itr.second + x[to]; int nt = t + 1; if(nt>k) nt = k; if(dp[to][nt]<=cost) continue; dp[to][nt] = cost; prev[to][nt] = make_pair(ni,t); que.push({cost,{to,nt}}); } } if(dp[t][k]==1e18){ cout<<"Impossible\n"; return 0; } cout<<"Possible\n"; cout<<dp[t][k]<<endl; vector<int> ans; ll ni = t; ll p = k; ans.push_back(ni); while(true){ auto nxt = prev[ni][p]; if(nxt.first==-1) break; ni = nxt.first; p = nxt.second; ans.push_back(ni); } cout<<ans.size()<<endl; reverse(ans.begin(),ans.end()); for(int i = 0;i<ans.size();i++){ if(i) cout<<" "; cout<<ans[i]+1; } cout<<endl; }