#1176624 (C++23) No.3616 WK vs AT vs MT vs SP

• 問題: No.3616 WK vs AT vs MT vs SP
• ユーザー: D M
• 提出日時: 2026-08-14 15:21:50
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 178 ms / 2,000 ms
• コード長: 3,553 bytes
• コンパイル時間: 4,375 ms
• コンパイル使用メモリ: 385,880 KB
• 実行使用メモリ: 40,556 KB
• 最終ジャッジ日時: 2026-08-14 15:22:02
• 合計ジャッジ時間: 9,250 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

サブタスク	配点	結果
サンプル	0 %	AC * 1
小課題1	8 %	AC * 9
小課題2	16 %	AC * 5
小課題3	20 %	AC * 10
小課題4	20 %	AC * 15
小課題5	20 %	AC * 15
小課題6	16 %	AC * 36
合計	2.5 * 100% = 250 点

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, limit) for (long long i = (long long)x; i < (long long)limit; i++)
#define REP(i, x, limit) for (long long i = (long long)x; i <= (long long)limit; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define el '\n'
#define spa " "
#define Yes cout << "Yes" << el
#define No cout << "No" << el
#define YES cout << "YES" << el
#define NO cout << "NO" << el
#define inp(x) for(auto &i:x)cin>>i
#define eps (1e-10)
#define Equals(a,b) (fabs((a) - (b)) < eps )
#define debug(x) cerr << #x << " = " << x << el
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;
using vb = vector<bool>;
const double pi = 3.141592653589793238;
const int inf = 1073741823;
const ll infl = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
const ll MOD = 998244353;
#include<atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using vm = vector<mint>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n,r,c;
    cin>>n>>r>>c;

    vl X(n),Y(n),Z(n),S(n);
    inp(X);
    inp(Y);
    inp(Z);
    inp(S);

    /*
        状態
        0 : 免許なし
        1 : AT
        2 : MT
        3 : 船舶
        4 : 船舶 + AT
        5 : 船舶 + MT

        頂点 i + n*k
        = 地点i、状態k

        hub
        6*n     : 船舶
        6*n + 1 : 船舶 + AT
        6*n + 2 : 船舶 + MT
    */

    ll sz=n*6+3;
    vector<vector<pll>> G(sz);

    // 道路
    rep(i,0,r){
        ll u,v,w,a,m;
        cin>>u>>v>>w>>a>>m;
        u--;
        v--;

        ll ca=min(w,a);
        ll cm=min({w,a,m});

        vl cost={
            w,      // 免許なし
            ca,     // AT
            cm,     // MT
            w,      // 船舶
            ca,     // 船舶 + AT
            cm      // 船舶 + MT
        };

        rep(j,0,6){
            ll U=u+n*j;
            ll V=v+n*j;

            G[U].push_back({V,cost[j]});
            G[V].push_back({U,cost[j]});
        }
    }

    rep(i,0,n){

        // AT免許取得
        G[i].push_back({i+n,X[i]});
        G[i+n*3].push_back({i+n*4,X[i]});

        // MT免許取得
        G[i].push_back({i+n*2,Y[i]});
        G[i+n].push_back({i+n*2,Y[i]});

        G[i+n*3].push_back({i+n*5,Y[i]});
        G[i+n*4].push_back({i+n*5,Y[i]});

        // 船舶免許取得
        G[i].push_back({i+n*3,Z[i]});
        G[i+n].push_back({i+n*4,Z[i]});
        G[i+n*2].push_back({i+n*5,Z[i]});


        // 船
        rep(j,0,3){
            ll v=i+n*(j+3);
            ll hub=n*6+j;

            // i -> hub
            G[v].push_back({hub,S[i]+c});

            // hub -> i
            G[hub].push_back({v,S[i]});
        }
    }


    // Dijkstra
    vl dist(sz,infl);

    priority_queue<
        pll,
        vector<pll>,
        greater<pll>
    > pq;

    dist[0]=0;
    pq.push({0,0});

    while(!pq.empty()){
        auto [d,v]=pq.top();
        pq.pop();

        if(dist[v]<d)continue;

        for(auto [to,cost]:G[v]){
            if(dist[to]>d+cost){
                dist[to]=d+cost;
                pq.push({dist[to],to});
            }
        }
    }


    // 地点Nに到着すれば免許状態は何でもよい
    ll ans=infl;

    rep(j,0,6){
        ans=min(ans,dist[n-1+n*j]);
    }

    cout<<ans<<el;
}