結果
問題 | 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;}