线段树优化建图
文章目录
题目描述
有 $n$ 个点和 $m$ 次操作,每一次操作为以下三种类型中的一种 :
1 u v dis:连一条 $u \to v$ 的单向边,权值为 $dis$。
2 u l r dis:对于所有 $i \in [l,r]$ 连一条 $u \to i$ 的单向边,权值为 $dis$。
3 u l r dis:对于所有 $i \in [l,r]$ 连一条 $i \to u$ 的单向边,权值为 $dis$。
$1 \le n \le 10^5$
简要做法
线段树优化建图
对于点 $[1,n]$,建一棵线段树
线段树采用动态开点,线段树节点编号从 $n + 1$ 开始
建两颗树,分别维护两个方向的边
对于线段树上每个节点,将它和它的左右儿子连条权值为 $0$ 的边
如果一个点和节点 $p$ 拉边,就间接和 $p$ 维护的区间上的点拉了边
参考代码
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <queue>
using ll = long long;
const ll N = 4e5 + 5;
const ll M = 3e6 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m, s;
ll head[N], num_edge;
ll ls[N], rs[N];
ll rt1, rt2, node_cnt;
ll dis[N];
bool vis[N];
struct Node
{
ll next, to, dis;
} edge[M];
struct data
{
ll cur, dis;
bool friend operator<(data a, data b) { return a.dis > b.dis; };
};
std::priority_queue<data> Q;
void add_edge(ll u, ll v, ll dis) { edge[++num_edge] = Node{head[u], v, dis}, head[u] = num_edge; }
void build(ll &p, ll l, ll r, ll opt)
{
if (l == r)
{
p = l;
return;
}
ll mid = (l + r) >> 1;
p = ++node_cnt;
build(ls[p], l, mid, opt), build(rs[p], mid + 1, r, opt);
if (opt == 0)
add_edge(p, ls[p], 0), add_edge(p, rs[p], 0);
else
add_edge(ls[p], p, 0), add_edge(rs[p], p, 0);
}
void update(ll &p, ll l, ll r, ll x, ll y, ll u, ll dis, ll opt)
{
if (x <= l and r <= y)
{
if (opt == 0)
add_edge(u, p, dis);
else
add_edge(p, u, dis);
return;
}
ll mid = (l + r) >> 1;
if (x <= mid)
update(ls[p], l, mid, x, y, u, dis, opt);
if (mid < y)
update(rs[p], mid + 1, r, x, y, u, dis, opt);
}
ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while ('0' > ch or ch > '9')
f = ch == '-' ? -1 : 1, ch = getchar();
while ('0' <= ch and ch <= '9')
x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
void dijkstra(ll s)
{
memset(dis, 0x3f, sizeof dis);
dis[s] = 0, Q.push(data{s, 0});
while (!Q.empty())
{
ll u = Q.top().cur;
Q.pop();
if (vis[u])
continue;
vis[u] = true;
for (ll i = head[u], v; i; i = edge[i].next)
if (dis[v = edge[i].to] > dis[u] + edge[i].dis)
{
dis[v] = dis[u] + edge[i].dis;
if (!vis[v])
Q.push(data{v, dis[v]});
}
}
}
signed main()
{
n = read(), m = read(), s = read();
node_cnt = n;
build(rt1, 1, n, 0), build(rt2, 1, n, 1);
for (ll u, v, dis, l, r, opt; m--;)
{
opt = read();
if (opt == 1)
v = read(), u = read(), dis = read(), add_edge(v, u, dis);
if (opt == 2)
v = read(), l = read(), r = read(), dis = read(), update(rt1, 1, n, l, r, v, dis, 0);
if (opt == 3)
v = read(), l = read(), r = read(), dis = read(), update(rt2, 1, n, l, r, v, dis, 1);
}
dijkstra(s);
for (ll i = 1; i <= n; i++)
printf("%lld ", dis[i] == INF ? -1 : dis[i]);
return 0;
}