发现可以线段树建图…
线段树建图 大概就是这样子…
众所周知 线段树的一个编号 (p) 指的是 ([L,R]) 这段区间
void buildto(int l , int r , int & p) { // 入边·线段树
if(l == r) { p = l ; return ; }
int mid = l + r >> 1 ; p = ++ cnt ;
buildto(l , mid , ls[p]) ; buildto(mid + 1 , r , rs[p]) ;
add(p , ls[p] , 0) ; add(p , rs[p] , 0) ;
}
(p) 指的是 ([L,R]) 这段区间的编号
(ls_p) 指的是 ([L,Mid]) 这段区间的编号
(rs_p) 指的是 ([Mid+1,R]) 这段区间的编号
初始化 (p) 向 (p) 的左儿子 和 (p) 的右儿子连边…
那么就间接完成了 (p) 向 ([L,R]) 地单独连边
即如果对 (p) 连边 就相当于对 ([L,R]) 连边…
（大概解释的够清楚了？）
所以这题可以建两颗线段树 一棵管入边 一棵管出边…
最后跑个最短路就出来了…
#include <bits/stdc++.h>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define rep(i , j , k) for(int i = j ; i <= k ; i ++)
#define Rep(i , j , k) for(int i = j ; i >= k ; i --)
using namespace std ;
using ll = long long ;
using pii = pair <int , int> ;
using vii = vector <int> ;
#define int long long
auto ot = [&]() { cerr << "ATS TXDY" << '
' ; int ATS_nantf_txdy = true ; } ;
auto _ios = [&]() { ios :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ; } ;
namespace stO_ATS_Orz {
template < class T > void cmax(T & x , T y) { if(x < y) x = y ; }
template < class T > void cmin(T & x , T y) { if(x > y) x = y ; }
template < class T > void abs(T x) { if(x < 0) x = -x ; }
const int N = 1e5 + 10 ;
int n , m , s ;
struct Node { int v , nxt , w ; } e[N * 30] ;
int rt1 , rt2 , cnt , head[N << 2] , ecnt = 0 , ls[N << 2] , rs[N << 2] , dis[N << 2] , vis[N << 2] ;
void add(int u , int v , int w) { e[++ ecnt] = {v , head[u] , w} ; head[u] = ecnt ; }
void buildto(int l , int r , int & p) { // 入边·线段树
if(l == r) { p = l ; return ; }
int mid = l + r >> 1 ; p = ++ cnt ;
buildto(l , mid , ls[p]) ; buildto(mid + 1 , r , rs[p]) ;
add(p , ls[p] , 0) ; add(p , rs[p] , 0) ;
}
void buildback(int l , int r , int & p) { // 出边·线段树
if(l == r) { p = l ; return ; }
int mid = l + r >> 1 ; p = ++ cnt ;
buildback(l , mid , ls[p]) ; buildback(mid + 1 , r , rs[p]) ;
add(ls[p] , p , 0) ; add(rs[p] , p , 0) ;
}
void upd(int a , int b , int l , int r , int u , int p , int w) { // 入边
if(a <= l && r <= b) { add(u , p , w) ; return ; }
int mid = l + r >> 1 ;
if(a <= mid) upd(a , b , l , mid , u , ls[p] , w) ;
if(b > mid) upd(a , b , mid + 1 , r , u , rs[p] , w) ;
}
void upd2(int a , int b , int l , int r , int u , int p , int w) { // 出边
if(a <= l && r <= b) { add(p , u , w) ; return ; }
int mid = l + r >> 1 ;
if(a <= mid) upd2(a , b , l , mid , u , ls[p] , w) ;
if(b > mid) upd2(a , b , mid + 1 , r , u , rs[p] , w) ;
}
void main() {
cin >> n >> m >> s ; cnt = n ; buildto(1 , n , rt1) ; buildback(1 , n , rt2) ;
while(m --) {
int opt ; cin >> opt ;
if(opt == 1) { int v , u , w ; cin >> v >> u >> w ; add(v , u , w) ; }
if(opt == 2) { int v , l , r , w ; cin >> v >> l >> r >> w ; upd(l , r , 1 , n , v , rt1 , w) ; }
if(opt == 3) { int v , l , r , w ; cin >> v >> l >> r >> w ; upd2(l , r , 1 , n , v , rt2 , w) ; }
}
queue < int > q ; memset(dis , 0x3f , sizeof(dis)) ; dis[s] = 0 ; q.push(s) ;
while(q.size()) {
int u = q.front() ; q.pop() ; vis[u] = 0 ;
for(int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(dis[v] > dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w ; if(! vis[v]) { q.push(v) ; vis[v] = 1 ; } }
}
}
for(int i = 1 ; i <= n ; i ++)
if(dis[i] == dis[0]) { cout << -1 << ' ' ; }
else { cout << dis[i] << ' ' ; }
}
}
signed main() {
_ios() ; ot() ;
return stO_ATS_Orz :: main() , 0 ;
}