結果

問題 No.3393 Move on Highway
コンテスト
ユーザー ゼリトキ
提出日時 2025-11-28 23:10:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 711 ms / 3,000 ms
コード長 2,537 bytes
コンパイル時間 3,479 ms
コンパイル使用メモリ 284,712 KB
実行使用メモリ 27,564 KB
最終ジャッジ日時 2025-11-28 23:10:57
合計ジャッジ時間 19,090 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long mod=998244353;
const long long mod100=1000000007;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int N,M;
    ll C;
    cin>>N>>M>>C;
    vector<pair<ll,int>>G[N+1];
    int u[M+1],v[M+1];
    ll w[M+1];
    for(int i=1;i<=M;i++){
        cin>>u[i]>>v[i]>>w[i];
        G[u[i]].push_back({w[i]+C,v[i]});
        G[v[i]].push_back({w[i]+C,u[i]});
    }
    bool already[N*2+1];
    ll dist1[N+1];
    for(int i=1;i<=N;i++){
        already[i]=0;
        dist1[i]=2e18;
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>PQ;
    PQ.push({0,1});
    dist1[1]=0;
    while(!PQ.empty()){
        int pos=PQ.top().second;
        ll cost=PQ.top().first;
        PQ.pop();
        if(already[pos]) continue;
        already[pos]=1;
        for(int i=0;i<G[pos].size();i++){
            int nex=G[pos][i].second;
            ll next_cost=G[pos][i].first+cost;
            if(already[nex]) continue;
            if(dist1[nex]>next_cost){
                dist1[nex]=next_cost;
                PQ.push({next_cost,nex});
            }
        }
    }
    ll dist2[N*2+1];
    for(int i=1;i<=N*2;i++){
        dist2[i]=2e18;
        already[i]=0;
    }
    PQ.push({0,N});
    dist2[N]=0;
    while(!PQ.empty()){
        int pos=PQ.top().second;
        ll cost=PQ.top().first;
        PQ.pop();
        if(already[pos]) continue;
        already[pos]=1;
        if(pos<=N){
            for(int i=0;i<G[pos].size();i++){
                int nex=G[pos][i].second;
                ll next_cost=G[pos][i].first+cost;
                if(already[nex]==0 && dist2[nex]>next_cost){
                    dist2[nex]=next_cost;
                    PQ.push({next_cost,nex});
                }
                if(already[nex+N]==0 && dist2[nex+N]>cost+C){
                    dist2[nex+N]=cost+C;
                    PQ.push({cost+C,nex+N});
                }
            }
        }
        else{
            pos-=N;
            for(int i=0;i<G[pos].size();i++){
                int nex=G[pos][i].second;
                ll next_cost=G[pos][i].first+cost;
                if(already[nex+N]==0 && dist2[nex+N]>next_cost){
                    dist2[nex+N]=next_cost;
                    PQ.push({next_cost,nex+N});
                }
            }
        }
    }
    for(int i=2;i<=N;i++){
        ll ans=min(dist1[N],dist1[i]+dist2[i+N]);
        cout<<ans<<endl;
    }
    
}
0