题目链接 Legacy
首先对于输入的$n$，建立一棵线段树。
显然线段树有大概$2n$个结点，每个节点对应一段区间
我们把这$2n$个结点加入我们的无向图中，一起跑最短路。
具体连边方案：
我们把这棵线段树复制一下，另外一棵倒过来。
首先第一棵线段树，每个结点向他的两个儿子连有向边，连到叶子结点的时候
叶子结点向原来的$n$个点连边
也就是说$[l, l]$向原来编号为$l$的这个点连边。
然后$1$到$n$这$n$个点分别向第二棵线段树的叶子结点分别连有向边
具体一点，$l$号点向$[l', l']$连边。
然后在第二棵线段树中，两个儿子向父亲连边，依次类推。
接着就是对给定的输入进行连边操作了。
对于点连向点的，普通操作就行了。
对于点连向区间的，把点连向第一棵线段树的结点。大概要连$logn$条边
对于区间连向点的，把第二棵线段树的结点连向这个点。大概也连$logn$条边
然后跑一边堆优化Dij就可以了。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((L + R) >> 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R
typedef long long LL;
typedef pair <int, int> PII;
const int N = 2e6 + 10;
struct node{
int u;
LL w;
friend bool operator < (const node &a, const node &b){
return a.w > b.w;
}
};
map <PII, int> mp;
int tot = 0;
int n, q, s, cnt;
LL dis[N];
vector <node> v[N];
void addedge(int x, int y, LL z){
v[x].push_back({y, z});
}
void build(int i, int L, int R){
cnt = max(cnt, i);
if (L == R){
addedge(i + n, L, 0);
return;
}
build(lson);
build(rson);
addedge(i + n, ls + n, 0);
addedge(i + n, rs + n, 0);
}
void build2(int i, int L, int R){
if (L == R){
addedge(L, i + n + cnt, 0);
return;
}
build2(lson);
build2(rson);
addedge(ls + n + cnt, i + n + cnt, 0);
addedge(rs + n + cnt, i + n + cnt, 0);
}
void work1(int i, int L, int R, int l, int r, int u, LL val){
if (l <= L && R <= r){
addedge(u, i + n, val);
return;
}
if (l <= mid) work1(lson, l, r, u, val);
if (r > mid) work1(rson, l, r, u, val);
}
void work2(int i, int L, int R, int l, int r, int u, LL val){
if (l <= L && R <= r){
addedge(i + n + cnt, u, val);
return;
}
if (l <= mid) work2(lson, l, r, u, val);
if (r > mid) work2(rson, l, r, u, val);
}
void dij(int s, LL dis[], vector <node> v[]){
priority_queue <node> q;
static bool vis[N];
rep(i, 1, 2e6) dis[i] = 1e18, vis[i] = false;
q.push({s, 0});
dis[s] = 0;
while (!q.empty()){
int u = q.top().u; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (auto edge : v[u]) if (dis[u] + edge.w < dis[edge.u]){
dis[edge.u] = dis[u] + edge.w;
q.push({edge.u, dis[edge.u]});
}
}
}
int main(){
scanf("%d%d%d", &n, &q, &s);
tot = n;
build(1, 1, n);
build2(1, 1, n);
while (q--){
int op;
scanf("%d", &op);
if (op == 1){
int x, y;
LL z;
scanf("%d%d%lld", &x, &y, &z);
if (x == y) continue;
addedge(x, y, z);
}
else if (op == 2){
int u, l, r;
LL z;
scanf("%d%d%d%lld", &u, &l, &r, &z);
work1(1, 1, n, l, r, u, z);
}
else{
int u, l, r;
LL z;
scanf("%d%d%d%lld", &u, &l, &r, &z);
work2(1, 1, n, l, r, u, z);
}
}
dij(s, dis, v);
rep(i, 1, n) printf("%lld
", (dis[i] < 1e18 ? dis[i] : -1));
return 0;
}