結果
問題 | No.1545 [Cherry 2nd Tune N] Anthem |
ユーザー |
![]() |
提出日時 | 2021-06-11 21:50:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 623 ms / 3,000 ms |
コード長 | 2,448 bytes |
コンパイル時間 | 3,709 ms |
コンパイル使用メモリ | 209,684 KB |
最終ジャッジ日時 | 2025-01-22 05:43:16 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 67 |
ソースコード
#include <bits/stdc++.h>using namespace std;using lii = pair<long long,pair<int,int>>;const long long inf = 1001001001001001001;bool chmin(long long &x,long long y) {if(x > y) {x = y;return true;}return false;}int main() {int N,S,T,K;cin >> N >> S >> T >> K;S--;T--;vector<int>X(N);for(int i = 0; i < N; i++) {cin >> X[i];}int M;cin >> M;vector<vector<pair<int,int>>>road(N),road2(N);for(int i = 0; i < M; i++) {int A,B,Y;cin >> A >> B >> Y;A--;B--;road[A].push_back({B,Y});road2[B].push_back({A,Y});}vector<vector<long long>>dist(N,vector<long long>(K+1,inf));dist[S][1] = X[S];priority_queue<lii,vector<lii>,greater<lii>>que;que.push({X[S],{S,1}});while (!que.empty()) {lii x = que.top();que.pop();long long cost = x.first;int n1 = x.second.first;int n2 = x.second.second;if(dist[n1][n2] != cost) {continue;}n2 = min(K,n2+1);for(int i = 0; i < road[n1].size(); i++) {int nxt = road[n1][i].first;long long cost2 = cost+road[n1][i].second+X[nxt];if(chmin(dist[nxt][n2],cost2)) {que.push({cost2,{nxt,n2}});}}}if(dist[T][K] == inf) {cout << "Impossible" << endl;}else {cout << "Possible" << endl;cout << dist[T][K] << endl;int n1 = T,n2 = K;vector<int>ans;ans.push_back(T+1);while (!(n1 == S && n2 == 1)) {for(int i = 0; i < road2[n1].size(); i++) {int nxt = road2[n1][i].first;long long cost = road2[n1][i].second+X[n1];if(dist[nxt][n2-1]+cost == dist[n1][n2]) {ans.push_back(nxt+1);n1 = nxt;n2 = n2-1;break;}if(dist[nxt][n2]+cost == dist[n1][n2]) {ans.push_back(nxt+1);n1 = nxt;n2 = n2;break;}}}reverse(ans.begin(),ans.end());cout << ans.size() << endl;for(int i = 0; i < ans.size(); i++) {cout << ans[i] << ((i+1 == ans.size())?"\n":" ");}}}