結果

問題 No.1545 [Cherry 2nd Tune N] Anthem
ユーザー fuppy_kyopro
提出日時 2021-06-11 22:09:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 172 ms / 3,000 ms
コード長 4,848 bytes
コンパイル時間 2,487 ms
コンパイル使用メモリ 215,144 KB
最終ジャッジ日時 2025-01-22 05:58:53
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 67
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//*/
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
#define DEBUG(x) cerr << #x << ": " << x << endl;
#define DEBUG_VEC(v) \
cerr << #v << ":"; \
for (int iiiiiiii = 0; iiiiiiii < v.size(); iiiiiiii++) \
cerr << " " << v[iiiiiiii]; \
cerr << endl;
#define DEBUG_MAT(v) \
cerr << #v << endl; \
for (int i = 0; i < v.size(); i++) { \
for (int j = 0; j < v[i].size(); j++) { \
cerr << v[i][j] << " "; \
} \
cerr << endl; \
}
typedef long long ll;
#define int ll
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define vs vector<string>
#define pii pair<int, int>
#define pis pair<int, string>
#define psi pair<string, int>
#define pll pair<ll, ll>
template <class S, class T>
pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) {
return pair<S, T>(s.first + t.first, s.second + t.second);
}
template <class S, class T>
pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template <class S, class T>
ostream &operator<<(ostream &os, pair<S, T> p) {
os << "(" << p.first << ", " << p.second << ")";
return os;
}
#define X first
#define Y second
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rrep1(i, n) for (int i = (int)(n); i > 0; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(), c.end()
void YES(bool t = true) {
cout << (t ? "YES" : "NO") << endl;
}
void Yes(bool t = true) { cout << (t ? "Yes" : "No") << endl; }
void yes(bool t = true) { cout << (t ? "yes" : "no") << endl; }
void NO(bool t = true) { cout << (t ? "NO" : "YES") << endl; }
void No(bool t = true) { cout << (t ? "No" : "Yes") << endl; }
void no(bool t = true) { cout << (t ? "no" : "yes") << endl; }
template <class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
int popcount(ll t) { return __builtin_popcountll(t); }
// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
// vi dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };
struct Setup_io {
Setup_io() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(25);
}
} setup_io;
// const ll MOD = 1000000007;
const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'
signed main() {
int n, s, t, k;
cin >> n >> s >> t >> k;
s--;
t--;
vi x(n);
rep(i, n) cin >> x[i];
int m;
cin >> m;
vector<vector<pll>> G(n);
rep(i, m) {
int u, v, y;
cin >> u >> v >> y;
u--;
v--;
G[u].emplace_back(v, y);
}
vll dp(n, vl(k + 1, INF));
vector<vector<pii>> pre(n, vector<pii>(k));
dp[s][0] = x[s];
pre[s][0] = pii(-1, -1);
using P = pair<ll, pii>;
priority_queue<P, vector<P>, greater<P>> pq;
pq.push(P(x[s], pii(s, 0)));
while (pq.size()) {
auto [cost, uk] = pq.top();
pq.pop();
auto [u, i] = uk;
if (dp[u][i] < cost) continue;
int ni = min(i + 1, k - 1);
for (auto [j, y] : G[u]) {
ll ncost = cost + y + x[j];
if (chmin(dp[j][ni], ncost)) {
pq.push(P(ncost, pii(j, ni)));
pre[j][ni] = pii(u, i);
}
}
}
if (dp[t][k - 1] == INF) {
cout << "Impossible" << endl;
return 0;
}
cout << "Possible" << endl;
cout << dp[t][k - 1] << endl;
vector<pii> his;
his.push_back(pii(t, k - 1));
while (true) {
auto [i, j] = his.back();
his.push_back(pre[i][j]);
if (his.back().first == -1) break;
}
his.pop_back();
reverse(all(his));
cout << his.size() << endl;
rep(i, his.size()) {
cout << his[i].first + 1 << " ";
}
cout << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0