# CFR 786 B. Legacy ( Dijkstra, Segment Tree )

Problem - B - Codeforces

1. u -> v : 代價 w
2. u -> [ L, R ] : 代價 w
3. [ L, R ] -> u : 代價 w

N, Q ≤ 1e5
w ≤ 1e9

ei1333.hateblo.jp

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;
}
```