CF 提交结果 Wrong answer on test 4。

#include <bits/stdc++.h>
typedef long long ll;
#define int long long

const int N = 1e5 + 10; 
const int inf = 1e18;

int n; 
struct node {
	int to, w;
} ;
std::vector <node> G[N << 3];
struct tree {
	int l, r;
} tree[N << 3];
int ls(int pos) { return pos << 1; }
int rs(int pos) { return pos << 1 | 1; }

int pos1[N], pos2[N], r2, e2;

void build1(int pos, int l, int r) {
	tree[pos].l = l; tree[pos].r = r;
	++ r2; 
	if (l == r) {
		pos1[l] = pos;
		return void();
	}
	int mid = l + r >> 1;
	build1(ls(pos), l, mid); build1(rs(pos), mid + 1, r);
	G[pos].push_back((node) {ls(pos), 0});
	G[pos].push_back((node) {rs(pos), 0});
	return void();
}
void build2(int pos, int l, int r) {
	tree[pos].l = l; tree[pos].r = r;
	++ e2; 
	if (l == r) {
		pos2[l] = pos;
		return void();
	}
	int mid = l + r >> 1;
	build2(ls(pos - (r2 - 1)) + r2 - 1, l, mid); build2(rs(pos - (r2 - 1)) + r2 - 1, mid + 1, r);
	G[ls(pos - (r2 - 1)) + pos1[n]].push_back((node) {pos, 0});
	G[rs(pos - (r2 - 1)) + pos1[n]].push_back((node) {pos, 0});
	return void();
}

void update1(int pos, int u, int l, int r, int val) {
	if (l <= tree[pos].l && tree[pos].r <= r) {
		G[u].push_back((node) {pos, val});
		return void();
	}
	int mid = tree[pos].l + tree[pos].r >> 1;
	if (l <= mid) update1(ls(pos), u, l, r, val);
	if (r > mid) update1(rs(pos), u, l, r, val);
	return void();
}
void update2(int pos, int u, int l, int r, int val) {
	if (l <= tree[pos].l && tree[pos].r <= r) {
		G[pos].push_back((node) {u, val});
		return void();
	}
	int mid = tree[pos].l + tree[pos].r >> 1;
	if (l <= mid) update2(ls(pos - (r2 - 1)) + (r2 - 1), u, l, r, val);
	if (r > mid) update2(rs(pos - (r2 - 1)) + (r2 - 1), u, l, r, val);
	return void();
}

int dis[N << 3];
bool vis[N << 3];
struct nd {
	int pos, dis;
	bool operator < (const nd &cmp) const {
		return dis > cmp.dis;
	}
} ; 
std::priority_queue <nd> q; 

void Dijkstra(int s, int e) {
	for (int i = 1; i <= e; ++ i) dis[i] = inf, vis[i] = 0;
	dis[s] = 0;
	q.push((nd) {s, 0});
	while (! q.empty()) {
		int u = q.top().pos; q.pop();
		if (vis[u]) continue ;
		vis[u] = 1; 
		for (int i = 0; i < G[u].size(); ++ i) {
			int v = G[u][i].to, w = G[u][i].w;
			if (dis[u] + w >= dis[v]) continue ;
			dis[v] = dis[u] + w; 
			q.push((nd) {v, dis[v]});
		}
	}
	return void();
}

signed main() {

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int s = 0, q = 0; 
	std::cin >> n >> q >> s;
	build1(1, 1, n);
	e2 = r2 ++; 
	build2(r2, 1, n);
	for (int i = 1; i <= n; ++ i) G[pos1[i]].push_back((node) {pos2[i], 0}), G[pos2[i]].push_back((node) {pos1[i], 0});
//	for (int i = 1; i <= n; ++ i) std::cout << pos2[i] << "\n";
	
//	for (int i = 1; i <= pos2[n]; ++ i) {
//		for (int j = 0; j < G[i].size(); ++ j) std::cout << G[i][j].to << " "; 
//		std::cout << "\n";
//	}
	while (q --> 0) { 
		int op, u, v, w, l, r;
		std::cin >> op;
		if (op == 1) std::cin >> u >> v >> w, G[pos1[u]].push_back((node) {pos1[v], w});
		if (op == 2) std::cin >> u >> l >> r >> w, update1(1, pos1[u], l, r, w);
		if (op == 3) std::cin >> u >> l >> r >> w, update2(r2, pos2[u], l, r, w);
	}
	
//	for (int i = 1; i <= pos2[n]; ++ i) {
//		for (int j = 0; j < G[i].size(); ++ j) std::cout << G[i][j].to << " ";
//		std::cout << "\n";
//	}
	
	Dijkstra(pos1[s], e2);
	for (int i = 1; i <= n; ++ i) std::cout << (dis[pos1[i]] == inf ? -1 : dis[pos1[i]]) << " ";
	std::cout << "\n";
	
	return 0;
}