【PGBATTLE2019_ましゅまろ4】ラッシュアワー

[Q] https://products.sint.co.jp/hubfs/resource/topsic/pgb/1-4.pdf
ダイクストラ。待ち時間のabsをうまく場合分けさえできればと思う。
これは、initの時点で、

D-|T-t| > K の t について。
-|T-t| > K-D
|T-t| <= D-K
|t-T| <= D-K
K-D <= t-T <= D-K
K-D+T <= t <= D-K+T

int left = -1, right = -1;
if (K-D <= D-K) {
   left = K-D+T;
   right = D-K+T;
}

「left ~ rightの時間の間は通行できない」の時間管理を抑えればわかりやすかったかもしれない。

dijkstraの中でabsを処理するなら以下。

// D-abs(T-t)<=K なら、その道を通ってok、
を整理する。
abs(T- t) > D - K が だめ だとわかる。
D-abs(T-t)は、tを動かすと、へ、の字の動きをする。折り返しがあるなら、t は折り返し分の距離 abs(T-t)*2を、即座に足してしまっていい。

    for(auto e : G[v]){ //e=next, cost
       // D-abs(T-t)<=K ならok
       // -abs(T-t)<=K-D
       // abs(T-t)>D-K
       // abs(T-cost)>konz-K ならok

       ll add = 0;
       if (abs(T-d[v]) <= e.konz-K){ // だめ
         if (T>d[v]) add = (T-d[v])*2; // 混雑度があがっていく おりかえす
         add += (e.konz-K) - abs(T-d[v]);
       }
       if (d[e.to] > d[v] + e.cost + add){
         d[e.to] = d[v] + e.cost + add;
         que.push(P(d[e.to], e.to));
         prev[e.to] = v; //vからe.toについた

実装

struct edge{ll to, cost, konz;};
typedef pair<ll, ll> P;
ll N, M, T, K;
struct graph{
 ll V;
 vector<vector<edge>> G;
 vector<ll> d;
 vector<ll> prev;
 vector<bool> used;
 graph(ll n){
   init(n);
 }
 void init(ll n){
   V = n;
   G.resize(V);
   d.resize(V);
   prev.resize(V);
   used.resize(n);
   rep(i, n) used[i] = false;
 }
 void add_edge(ll s, ll t, ll cost, ll konz){
   edge e;
   e.to = t, e.cost = cost;
   e.konz = konz;
   G[s].push_back(e);
 }
 void del_edge(ll s, ll t, ll cost){
   for (auto it = G[s].begin(); it != G[s].end();){
     if ((*it).to == t && (*it).cost == cost)
       it = G[s].erase(it);
     else
       it++;
   }
 }
 ll get_edgesize(ll s){
   ll size = 0;
   for(auto v: G[s]){
     if (used[v.to]) continue;
     used[v.to] = true;
     size++;
     size += get_edgesize(v.to);
   }
   return size;
 }
 
 //経路はprevに
 void dijkstra(ll s){
   rep(i, V){
     d[i] = oo;
     prev[i] = -1;
   }
   d[s] = 0;
   priority_queue<P, vector<P>, greater<P>> que;
   que.push(P(0, s)); //cost, v
   while(!que.empty()){
     P p = que.top(); que.pop();
     ll v = p.second;
     if(d[v] < p.first) continue;
     for(auto e : G[v]){ //e=next, cost
       // D-abs(T-t)<=K
       // -abs(T-t)<=K-D
       // abs(T-t)>D-K
       // abs(T-cost)>konz-Kならok
       ll add = 0;
       if (abs(T-d[v]) <= e.konz-K){ // だめ
         if (T>d[v]) add = (T-d[v])*2; // 混雑度があがっていく おりかえす
         add += (e.konz-K) - abs(T-d[v]);
       }
       if (d[e.to] > d[v] + e.cost + add){
         d[e.to] = d[v] + e.cost + add;
         que.push(P(d[e.to], e.to));
         prev[e.to] = v; //vからe.toについた
       }
     }
   }
 }  
 
 vector<ll> get_path(int g, int s) {
   // s 1->2->3 g
   // path[0]=1 path[1]=2 path[2]=3 を返す
   vector<ll> path;
   for (int cur = g; cur != s; cur = prev[cur]) { // goalまで
       path.push_back(cur);
   }
   path.push_back(s);
   reverse(path.begin(), path.end()); // 逆順なのでひっくり返す
   return path;
 }
};
int main(){
 cincout();
 
 cin >> N >> M >> T >> K;
 graph g(N+1); // 0index ~ 
 // 戻り道
 rep(i, M){
   ll A, B, C, D;
   cin >> A >> B >> C >> D;
   --A, --B;
   g.add_edge(B, A, C, D);
   g.add_edge(A, B, C, D);
 }
 g.dijkstra(0);
 if (g.d[N-1] == oo)
   cout << -1 << endl;
 else
   cout << g.d[N-1] << endl;
}

もしくは left ~ rightでとる場合

​ void dijkstra(ll s){
   rep(i, V){
     d[i] = oo;
     prev[i] = -1;
   }
   d[s] = 0;
   priority_queue<P, vector<P>, greater<P>> que;
   que.push(P(0, s)); //cost, v
   while(!que.empty()){
     P p = que.top(); que.pop();
     ll v = p.second;
     if(d[v] < p.first) continue;
     for(auto e : G[v]){ //e=next, cost
       ll nx = d[v]+e.cost;
       if (d[v] < e.right && nx > e.left) chmax(nx, e.right+e.cost);
       if(d[e.to] > nx){
         d[e.to] = nx;
         que.push(P(d[e.to], e.to));
         prev[e.to] = v; //vからe.toについた
       }
     }
   }
 }  

int main(){
 cin.tie(0);
 ios::sync_with_stdio(0);
 cout << fixed << setprecision(10);
 
 ll N, M, T, K;
 cin >> N >> M >> T >> K;
 graph g(N+1); // 0index ~ 
 // 戻り道
 rep(i, M){
   ll A, B, C, D;
   cin >> A >> B >> C >> D;
   --A, --B;
   // D-|T-t| > K のtについて。
   // |T-t| <= D-K
   // |t-T| <= D-K
   // K-D <= t-T <= D-K
   // K-D+T <= t <= D-K+T
   
   ll left=-1, right=-1;
   if (K-D <= D-K){
     left = K-D+T;
     right = D-K+T;
   }
   g.add_edge(A, B, C, left, right);
   g.add_edge(B, A, C, left, right);
 }
 g.dijkstra(0);
 if (g.d[N-1] == oo)
   cout << -1 << endl;
 else
   cout << g.d[N-1] << endl;
}
​