結果

問題 No.3393 Move on Highway
コンテスト
ユーザー toppo57
提出日時 2026-10-31 15:28:44
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc16.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 210 ms / 3,000 ms
+ 335µs
コード長 1,821 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,686 ms
コンパイル使用メモリ 208,772 KB
実行使用メモリ 26,312 KB
最終ジャッジ日時 2026-10-31 15:29:03
合計ジャッジ時間 14,216 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
using ll = long long;
using P = pair<ll, int>;
using P2 = pair<ll, pair<int, int>>;
using Graph = vector<vector<pair<int, ll>>>;
const ll INF = 1LL<<60;

int N, M; ll C;

Graph G(200010);
ll D_st[200010], D_en[200010][2];

void Dijkstra1(int src){
    fill(&D_st[0], &D_st[0]+200010, INF);
    D_st[src]=0;
    priority_queue<P, vector<P>, greater<P>> Q;
    Q.push({0, src});

    while(! Q.empty()){
        auto [dist, cur] = Q.top();
        Q.pop();
        if (dist>D_st[cur]) continue;
        for (auto [dst, w]: G[cur]){
            if(dist+w+C<D_st[dst]){
                Q.push({D_st[dst]=dist+w+C, dst});
            }
        }
    }
}

void Dijkstra2(int src){
    fill(&D_en[0][0], &D_en[0][0]+200010*2, INF);
    D_en[src][0]=0, D_en[src][1]=0;
    priority_queue<P2, vector<P2>, greater<P2>> Q;
    Q.push({0, make_pair(src, 0)});
    Q.push({0, make_pair(src, 1)});

    while(! Q.empty()){
        auto [dist, p] = Q.top();
        Q.pop();
        auto [cur, used] = p;
        if (dist>D_en[cur][used]) continue;
        for (auto [dst, w]: G[cur]){
            if(used==0 && dist+C<D_en[dst][1]){
                Q.push({D_en[dst][1]=dist+C, make_pair(dst, 1)});
            }
            if(dist+w+C<D_en[dst][used]){
                Q.push({D_en[dst][used]=dist+w+C, make_pair(dst, used)});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N>>M>>C;
    for (int i=0;i<M;i++){
        int U, V; ll W;
        cin>>U>>V>>W;
        G[U].push_back({V, W});
        G[V].push_back({U, W});
    }

    Dijkstra1(1);
    Dijkstra2(N);

    for (int i=2;i<=N;i++){
        cout << min(D_st[N], D_st[i]+D_en[i][1]) << "\n";
    }
    
    return 0;
}
0