#1186289 (C++23) No.3712 Urban Train

• 問題: No.3712 Urban Train
• ユーザー: kuronosu1024
• 提出日時: 2026-09-11 22:27:38
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 247 ms / 2,000 ms
• コード長: 3,689 bytes
• コンパイル時間: 2,267 ms
• コンパイル使用メモリ: 349,164 KB
• 実行使用メモリ: 20,400 KB
• 最終ジャッジ日時: 2026-09-11 22:27:54
• 合計ジャッジ時間: 5,963 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 39

ソースコード

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN

#include __FILE__

int main(void){
    int n, m; cin >> n >> m;
    vector<vector<pair<ll,int>>> nb(n);
    int i ;
    rep(i,m){
        int u, v, w; cin >> u >> v >> w;
        u--;v--;
        nb[u].push_back({w,v});
        nb[v].push_back({w,u});
    }
    rep(i,n){
        sort(all(nb[i]));
    }
    vector<ll> a(n), b(n), c(n);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    rep(i,n) cin >> c[i];

    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>> > pq;
    pq.push({1,0});
    vector<ll> v(n,-1);
    v[0] = 1;

    while(!pq.empty()){
        auto [t,x] = pq.top(); pq.pop();
        if(v[x] < t) continue;

        i = x;
        for(auto [nw,nx] : nb[x]){
            ll nt = (t+a[i]-1)/a[i]*a[i] + nw;
            if((t+a[i]-1)/a[i] %b[i] == 0){
                nt = min(nt + c[i], nt + a[i]);
            }
            
            if(v[nx] == -1 || v[nx] > nt){
                v[nx] = nt;
                pq.push({nt,nx});
            }
        }
    }

    cout << v[n-1] << "\n";

}

#else
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld=  long double;
#define rep(i,n) for(i=0;i<(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

int randint(int a, int b){
    static mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> dist(a,b);
    return dist(gen);
}

namespace nskr{
    template <int id = 0>
    struct modint{
        int v;

        static int& MOD(){
            static int mod = 998244353;
            return mod;
        }

        static int get_mod() { return MOD(); }
        static void set_mod(int m) { MOD() = m; }

        modint() :v(0){}
        modint(long long x) : v( (x>=0 ? x%MOD() : (x%MOD() + MOD()))){}

        long long val() const {return v;}

        modint& operator+=(const modint& x){if((v+=x.v) >= MOD()) v-=MOD(); return *this; }
        modint& operator-=(const modint& x){if((v-=x.v) <  0  ) v+=MOD(); return *this; }
        modint& operator*=(const modint& x){v = (int)(1ll * v * x.v % MOD()); return *this;}
        modint& operator/=(const modint& x){v = (int)(1ll * v * x.inv().val() % MOD()); return *this;}

        modint operator-() const {return modint(-v);}
        modint operator+() const {return *this;}

        modint operator+(const modint& x) const {return modint(*this)+=x;}
        modint operator-(const modint& x) const {return modint(*this)-=x;}
        modint operator*(const modint& x) const {return modint(*this)*=x;}
        modint operator/(const modint& x) const {return modint(*this)/=x;}

        bool operator== (const modint& x) const {return v==x.v;}
        bool operator!= (const modint& x) const {return v!=x.v;}

        friend ostream &operator<<(ostream &os, const modint &p) { return os << p.v; }

        friend istream &operator>>(istream &is, modint &a) {
            int t;
            is >> t;
            a = modint<id>(t);
            return (is);
        }


        modint pow(unsigned long long n) const { 
            modint ret(1), mul(v);
            while(n){
                if(n&1) ret *= mul;
                mul *= mul;
                n >>=1;
            }
            return ret;
        }

        modint inv() const{ //参考：　https://qiita.com/sesame0224/items/f2ac77c367f588c0d29d
            int a = v, b = MOD(), u = 1, w = 0;
            while(b){
                int t = a/b;                 
                swap(a -= t*b, b);
                swap(u -= t*w, w);
            }
            u%=MOD();
            return(u<0?u+MOD():u);
        }


    };

}



#endif