CFR 786 B. Legacy ( Dijkstra, Segment Tree )

Problem - B - Codeforces

題意：
給一張圖，N 個點，Q 個邊，起點 S。
邊有三種，各自用 u, v / L, R, w 描述：
1. u -> v : 代價 w
2. u -> [ L, R ] : 代價 w
3. [ L, R ] -> u : 代價 w
問所有終點的單源最短路徑，不存在則輸出 -1。

資料規模：
N, Q ≤ 1e5
w ≤ 1e9

解法：
首先顯然 [ L, R ] 是連續的，這個性質非常重要。因為如果不是連續的而能解出來，那等於是要給出比理論最快的單源最短路徑算法還快的算法。如果只有操作 1 和 2，那麼可以用線段樹直接做區間極值詢問和單點修改。但是由於有操作 3，不得不考慮別的作法。
據說這是「很常用」的技巧，但我真的是第一次聽說，覺得很神奇。
考慮在線段樹上的節點之間連邊。
可以參考這一篇的圖片，非常容易理解。
ei1333.hateblo.jp
轉換為線段樹上的節點上的最短路徑問題之後，節點數量是 O( N lg N )，邊的數量是 O( Q lg N )，因此可以用 Dijkstra 算法解決。
注意，在線段樹上向上和向下的花費為 0，但不是所有情況都可以任意向上向下移動。觀察一番後，可以發現只要設定成無花費往同一個方向移動後，不能立刻接著無花費往反方向移動。

時間 / 空間複雜度：
O( N lg^2 N ) / O( N lg N )

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

template< class T1, class T2 >
bool upmin( T1 &x, T2 v ){
  if( x <= v ) return 0;
  x = v; return 1;
}

const int MAXN = ( int ) 1e5;

int N, Q, S;
vector< pair< int, int > > to[ MAXN << 3 ];

long long dis[ MAXN << 3 ][ 3 ];

int find( int t, int lb, int rb, int u ){
  if( lb + 1 == rb ) return t;
  int mid = lb + rb >> 1;
  if( u < mid ) return find( t << 1, lb, mid, u );
  return find( t << 1 | 1, mid, rb, u );
}

void add_edge( int t, int lb, int rb, int ql, int qr, int u, int w, int to_range ){
  if( qr <= lb or rb <= ql ) return;
  if( ql <= lb and rb <= qr ){
    if( to_range ){
      to[ u ].emplace_back( w, t );
    } else{
      to[ t ].emplace_back( w, u );
    }
    return;
  }
  int mid = lb + rb >> 1;
  add_edge( t << 1, lb, mid, ql, qr, u, w, to_range );
  add_edge( t << 1 | 1, mid, rb, ql, qr, u, w, to_range );
}

signed main(){
  ios::sync_with_stdio( 0 );
  { // input
    cin >> N >> Q >> S;
    --S; // 0 base
    for( int qi = 0; qi < Q; ++qi ){
      int op; cin >> op;
      if( op == 1 ){
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        to[ find( 1, 0, N, u ) ].emplace_back( w, find( 1, 0, N, v ) );
      } else if( op == 2 ){
        int u, l, r, w;
        cin >> u >> l >> r >> w;
        --u, --l; // [ l, r )
        add_edge( 1, 0, N, l, r, find( 1, 0, N, u ), w, 1 );
      } else{
        int u, l, r, w;
        cin >> u >> l >> r >> w;
        --u, --l;
        add_edge( 1, 0, N, l, r, find( 1, 0, N, u ), w, 0 );
      }
    }
  }
  {
    for( int i = 0; i < N << 3; ++i ){
      for( int j = 0; j < 3; ++j ){
        dis[ i ][ j ] = 1LL << 50;
      }
    }
    priority_queue< tuple< long long, int, int > > pq;
    pq.emplace( dis[ find( 1, 0, N, S ) ][ 0 ] = 0LL, find( 1, 0, N, S ), 0 );
    while( not pq.empty() ){
      long long d;
      int u, f;
      tie( d, u, f ) = pq.top();
      d *= -1;
      pq.pop();
      if( d != dis[ u ][ f ] ) continue;
      if( f != 2 ){ // 上がっていいよ
        if( u != 1 and upmin( dis[ u >> 1 ][ 1 ], d ) ){
          pq.emplace( - dis[ u >> 1 ][ 1 ], u >> 1, 1 );
        }
      }
      if( f != 1 ){ // 下がっていいよ
        if( u << 1 < N << 3 and upmin( dis[ u << 1 ][ 2 ], d ) ){
          pq.emplace( - dis[ u << 1 ][ 2 ], u << 1, 2 );
        }
        if( ( u << 1 | 1 ) < N << 3 and upmin( dis[ u << 1 | 1 ][ 2 ], d ) ){
          pq.emplace( - dis[ u << 1 | 1 ][ 2 ], u << 1 | 1, 2 );
        }
      }
      for( int ei = 0; ei < to[ u ].size(); ++ei ){
        int w, v;
        tie( w, v ) = to[ u ][ ei ];
        if( upmin( dis[ v ][ 0 ], d + w ) ){
          pq.emplace( - dis[ v ][ 0 ], v, 0 );
        }
      }
    }
  }
  {
    for( int i = 0; i < N; ++i ){
      int t = find( 1, 0, N, i );
      long long d = min( { dis[ t ][ 0 ], dis[ t ][ 1 ], dis[ t ][ 2 ] } );
      if( d == 1LL << 50 ){
        cout << -1;
      } else{
        cout << d;
      }
      cout << " \n"[ i + 1 == N ];
    }
  }
  return 0;
}