結果

問題 No.1 道のショートカット
コンテスト
ユーザー vjudge1
提出日時 2026-01-06 14:29:02
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 2,662 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,027 ms
コンパイル使用メモリ 361,032 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-06 14:29:09
合計ジャッジ時間 5,733 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#ifdef croquete  // BEGIN TEMPLATE ----------------------|
#include "dbg/dbg.h"
#define fio freopen("in.txt", "r", stdin)
#else
#define dbg(...)
#define fio cin.tie(0)->sync_with_stdio(0)
#endif
#define ll           long long
#define vll          vector<ll>
#define vvll         vector<vll>
#define pll          pair<ll, ll>
#define vpll         vector<pll>
#define all(xs)      xs.begin(), xs.end()
#define rep(i, a, b) for (ll i = (a); i  < (ll)(b); ++i)
#define per(i, a, b) for (ll i = (a); i >= (ll)(b); --i)
#define eb           emplace_back
#define cinj         cin.iword(0)  = 1, cin
#define coutj        cout.iword(0) = 1, cout
template <typename T>  // read vector
istream& operator>>(istream& is, vector<T>& xs) {
    assert(!xs.empty());
    rep(i, is.iword(0), xs.size()) is >> xs[i];
    return is.iword(0) = 0, is;
} template <typename T>  // print vector
ostream& operator<<(ostream& os, vector<T>& xs) {
    rep(i, os.iword(0), xs.size()) os << xs[i] << ' ';
    return os.iword(0) = 0, os;
} void solve();
signed main() {
    fio;
    ll t = 1;
    // cin >> t;
    while (t--) solve();
}  // END TEMPLATE --------------------------------------|

// BEGIN EXTRAS -----------------------------------------|
#define ull unsigned ll
#define vvvll vector<vvll>
#define vvpll vector<vpll>
#define tll   tuple<ll, ll, ll>
#define vtll  vector<tll>
#define pd    pair<double, double>
#define x     first
#define y     second
map<char, pll> ds1 { {'R', {0, 1}}, {'D', {1, 0}}, {'L', {0, -1}}, {'U', {-1, 0}} };
vpll ds2 { {0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1,  1}, {1, -1}, {-1,  1}, {-1, -1} };
vpll ds3 { {1, 2}, {2, 1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1} };
// END EXTRAS -------------------------------------------|

ll dijkstra(const vector<vtll>& g, ll s, ll c) {
    vvll ds(g.size(), vll(c + 1, LLONG_MAX));
    priority_queue<tll, vtll, greater<>> pq;
    ds[s][0] = 0, pq.emplace(ds[s][0], 0, s);
    while (!pq.empty()) {
        auto [t, cc, u] = pq.top(); pq.pop();
        if (t > ds[u][cc]) continue;
        for (auto [w, ccc, v] : g[u]) {
            ll nc = cc + ccc;
            if (nc <= c && t + w < ds[v][nc]) {
                ds[v][nc] = t + w;
                pq.emplace(ds[v][nc], nc, v);
            }
        }
    }
    return *min_element(all(ds.back()));
}

void solve() {
    ll n, c, v;
    cin >> n >> c >> v;
    vector<vtll> g(n + 1);
    vll s(v), t(v), y(v), m(v);
    cin >> s >> t >> y >> m;
    rep(i, 0, v) g[s[i]].eb(m[i], y[i], t[i]);
    ll ans = dijkstra(g, 1, c);
    if (ans == LLONG_MAX) cout << "-1\n";
    else cout << ans << '\n';
}
0