don't be late [技術室奥プログラミングコンテスト#4 Day1 H]

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_h

前提知識

• ダイクストラ

解説

https://atcoder.jp/contests/tkppc4-1/submissions/6664209

無向グラフで最短時間といえばダイクストラである。
実際それ以外で解くにはいろいろ尖った形にする必要がある。
ダイクストラの枠組みで考えてみると解ける。
dist[cu] := 駅cuに到達するための最短時間

int N, M;
ll K;
int T[201010];
using Edge = tuple<int, int, int>;
vector<Edge> E[201010];
bool vis[201010];
ll dist[201010];
//---------------------------------------------------------------------------------------------------
ll djik() {
    min_priority_queue<pair<ll, int>> que;

    rep(i, 0, N) dist[i] = infl;
    dist[0] = 0;
    que.push({ 0, 0 });

    while (!que.empty()) {
        auto q = que.top(); que.pop();

        ll cst = q.first;
        int cu = q.second;

        if (vis[cu]) continue;
        vis[cu] = true;

        if (cu == N - 1) return cst;

        cst += T[cu];

        fore(e, E[cu]) {
            int to, c, d;
            tie(to, c, d) = e;

            ll cst2 = cst;
            if (0 < cst2 % d) cst2 += (d - (cst2 % d));
            cst2 += c;

            if (chmin(dist[to], cst2)) que.push({ dist[to], to });
        }
    }

    return infl;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 1, N - 1) cin >> T[i];
    rep(i, 0, M) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        a--; b--;
        E[a].push_back(Edge(b, c, d));
        E[b].push_back(Edge(a, c, d));
    }

    ll ans = djik();
    if (K < ans) ans = -1;
    cout << ans << endl;
}