結果

問題 No.1545 [Cherry 2nd Tune N] Anthem
ユーザー KKT89
提出日時 2021-06-12 03:28:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 249 ms / 3,000 ms
コード長 1,951 bytes
コンパイル時間 11,321 ms
コンパイル使用メモリ 286,880 KB
最終ジャッジ日時 2025-01-22 07:40:45
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 67
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:64:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wformat=]
   64 |         printf("%d\n",v.size());
      |                 ~^    ~~~~~~~~
      |                  |          |
      |                  int        std::vector<int>::size_type {aka long unsigned int}
      |                 %ld

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int 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<int,ll>>> g(n);
    int m; cin >> m;
    for(int i=0;i<m;i++){
        int a,b,y; cin >> a >> b >> y;
        a--; b--;
        g[a].push_back({b,y});
    } 
    const ll INF=1e18;
    vector<vector<ll>> d(n,vector<ll>(k,INF));
    vector<vector<pair<int,int>>> rev(n,vector<pair<int,int>>(k,{-1,-1})); 
    d[s][0]=x[s];
    priority_queue<pair<ll,pair<int,int>>,vector<pair<ll,pair<int,int>>>,greater<pair<ll,pair<int,int>>>> pq;
    pq.push({d[s][0],{s,0}});
    while(pq.size()){
        auto p=pq.top(); pq.pop();
        int ss=p.second.first,cn=p.second.second;
        if(p.first!=d[ss][cn])continue;
        for(auto to:g[ss]){
            ll cost=p.first+to.second+x[to.first];
            int nxt=to.first;
            int nxc=min(k-1,cn+1);
            if(cost<d[nxt][nxc]){
                d[nxt][nxc]=cost;
                rev[nxt][nxc]={ss,cn};
                pq.push({d[nxt][nxc],{nxt,nxc}});
            }
        }
    }
    if(d[t][k-1]==INF){
        printf("Impossible\n");
    }
    else{
        printf("Possible\n");
        printf("%lld\n",d[t][k-1]);
        auto p=rev[t][k-1];
        vector<int> v={t};
        while(p.second>=0){
            int nxt=p.first,nxc=p.second;
            v.push_back(nxt);
            p=rev[nxt][nxc];
        }
        reverse(v.begin(), v.end());
        printf("%d\n",v.size());
        for(int i=0;i<v.size();i++){
            printf("%d ",v[i]+1);
        }
        printf("\n");
    }

}
0