CF786B.Legacy
留着以后复习
#include <iostream>
#include <cstring>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
using i64 = long long;
using PII = pair<i64, int>;
const int N = 100010, M = 5000010, P = 400000;
const i64 INF = 1e18;
struct Node {
int l, r;
}tr[N << 3]; // 两棵树一起开 同一个真实结点在两棵树里面的叶子结点编号差值相同 用偏移量
int e[M], ne[M], h[N << 3], idx;
int w[M];
int mp[N]; // 真实结点编号到线段树结点编号的映射
int n, m, S;
i64 dis[N << 3]; // 不开longlong见祖宗
bool vis[N << 3];
void insert(int u, int v, int d) {
e[idx] = v, ne[idx] = h[u], w[idx] = d, h[u] = idx++;
}
void build(int u, int l, int r) {
tr[u] = {l, r};
if (l == r) return void(mp[l] = u);
int mid = l + r >> 1;
insert(u, u << 1, 0), insert(u, u << 1 | 1, 0); // 出树往子节点连
insert((u << 1) + P, u + P, 0), insert((u << 1 | 1) + P, u + P, 0); // 入树往父节点连
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int v, int w, int op) {
if (tr[u].l >= l && tr[u].r <= r) { // 连边区间完全包含结点区间
if (op == 2) insert(v + P, u, w); // 入树叶子结点连出树区间结点
if (op == 3) insert(u + P, v, w); // 入树区间结点连出树叶子结点
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, v, w, op);
if (r > mid) modify(u << 1 | 1, l, r, v, w, op);
}
int main() {
cin.tie(0), cout.tie(0)->sync_with_stdio(false);
cin >> n >> m >> S;
memset(h, -1, sizeof h);
build(1, 1, n);
for (int i = 1; i <= n; i++) {
insert(mp[i], mp[i] + P, 0);
insert(mp[i] + P, mp[i], 0); // 入树出树叶子结点互连
}
while (m--) {
int op, u, v, l, r, w;
cin >> op;
if (op == 1) cin >> u >> v >> w, insert(mp[u] + P, mp[v], w); // 单点连单点直接连
else cin >> v >> l >> r >> w, modify(1, l, r, mp[v], w, op);
}
function<void(int)> dijkstra = [&](int S) {
memset(dis, 0x3f, sizeof dis);
priority_queue<PII, vector<PII>, greater<PII>> heap;
dis[S] = 0;
heap.push({0, S});
while (heap.size()) {
auto tt = heap.top();
heap.pop();
int t = tt.second;
if (vis[t]) continue;
vis[t] = true;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[t] + w[i]) {
dis[j] = dis[t] + w[i];
heap.push({dis[j], j});
}
}
}
};
dijkstra(mp[S] + P);
for (int i = 1; i <= n; i++) {
if (dis[mp[i]] > INF / 2) cout << "-1 ";
else cout << dis[mp[i]] << ' ';
}
return 0;
}