https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-4.pdf
前提知識
解説
入力例で正しいことしか確認できていません！落ちる可能性ありますので、ご注意ください
rep(i,a,b)はfor (int i=a; i < b; i++)です。
都市と道路の関係性は無向グラフに置き換えることができる。
無向グラフ上での最短距離といえば、有名なダイクストラというアルゴリズムがあるので、それを適用して解く。
ダイクストラについては競技プログラミングで解説が充実しているので、そちらで学習しよう。
今回の問題では、ベースとなるダイクストラのアルゴリズムの遷移部分に手を加えることで解いていく。
このように競技プログラミングでは、既存のアルゴリズムをベースとして目的のアルゴリズムを形成する能力を要求するものもある。
遷移できるかどうかの判定に混雑度がKを超える瞬間があるかどうかを判定したい。
移動できない時間について立式して式変形していく。
K < Di - |T - t|
|T - t| < Di - K
- Di + K < T - t < Di - K
- Di + K - T < -t < Di - K - T
-Di + K + T < t < Di - K + T
各道路でこの時間は通れないことになる。
ある時刻sで道路をスタートすると道路を通っている時間は[s,s+C[i]]となる。
この時間と(-Di + K + T, Di - K + T)がかぶっているなら、ラッシュアワーが終わるまで待ってから出発する。
両方とも開区間（=がつかない）のは扱いにくいので+1,-1して
[s,s+C[i]]と[-Di+K+T+1,Di-K+T-1]がかぶるかどうか判定する。
この判定は、かぶっていないことを判定する方が楽。
あとは、普通のダイクストラと同じ。
（出発の時間もかぶったら駄目って感じで実装したけど、それで合ってるんだろうか。サンプルは合うけど）
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() //#pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } //--------------------------------------------------------------------------------------------------- template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>; /*--------------------------------------------------------------------------------------------------- ∧＿∧ ∧＿∧ （´<_｀ ） Welcome to My Coding Space! （ ´_ゝ`） / ⌒i @hamayanhamayan ／ ＼ | | / /￣￣￣￣/ | ＿_(__ﾆつ/ ＿/ .| .|＿＿＿＿ ＼/＿＿＿＿/ （u ⊃ ---------------------------------------------------------------------------------------------------*/ int N, M, T, K, A[101010], B[101010], C[101010], D[101010]; vector<pair<int, int>> E[101010]; bool vis[101010]; ll tim[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> T >> K; rep(i, 0, M) cin >> A[i] >> B[i] >> C[i] >> D[i]; rep(i, 0, M) { int a = A[i]; int b = B[i]; E[a].push_back({b, i}); E[b].push_back({a, i}); } rep(i, 1, N + 1) tim[i] = infl; rep(i, 1, N + 1) vis[i] = false; min_priority_queue<pair<ll, int>> que; tim[1] = 0; que.push({ 0, 1 }); while (!que.empty()) { auto q = que.top(); que.pop(); ll cst = q.first; int cu = q.second; if (vis[cu]) continue; vis[cu] = true; fore(p, E[cu]) { int to = p.first; int c = C[p.second]; int d = D[p.second]; int rush_lft = -d + K + T + 1; int rush_rht = d - K + T - 1; ll move_lft = cst; ll move_rht = cst + c; ll cst2 = cst + c; if (rush_lft <= rush_rht) { bool ok1 = move_rht < rush_lft; bool ok2 = rush_rht < move_lft; if (!ok1 and !ok2) cst2 = rush_rht + c + 1; } if (chmin(tim[to], cst2)) que.push({ tim[to], to }); } } if (tim[N] == infl) tim[N] = -1; cout << tim[N] << endl; }
