C F 786 B ? L e g a c y \mathrm{CF786B - Legacy} CF786B?Legacy

D e s c r i p t i o n \mathrm{Description} Description

給定 $1$ 張 $n$ 個(gè)點(diǎn)的有向圖，初始沒(méi)有邊，接下來(lái)有 $q$ 次操作，形式如下：

• 1 u v w 表示從 $u$ 向 $v$ 連接 $1$ 條長(zhǎng)度為 $w$ 的有向邊
• 2 u l r w 表示從 $u$ 向 $i$（$i\in [l,r]$）連接 $1$ 條長(zhǎng)度為 $w$ 的有向邊
• 3 u l r w 表示從 $i$（$i\in [l,r]$）向 $u$ 連接 $1$ 條長(zhǎng)度為 $w$ 的有向邊

輸出從 $S$ 點(diǎn)到 $i$ 點(diǎn)（$i\in [1,n]$）的最短路長(zhǎng)度。

S o l u t i o n \mathrm{Solution} Solution

觀察可知，最多會(huì)建立 $10^5\times 10^5=10^{10}$ 條邊，故必定超時(shí)。

此時(shí)，需要使用 線段樹(shù)優(yōu)化建圖，這里展開(kāi)簡(jiǎn)單說(shuō)一下：

對(duì)于 $1$ 棵存儲(chǔ)點(diǎn)為 $1～4$ 的線段樹(shù)，形式如下：

如果當(dāng)前為 $2$ 操作，且為 $1～3$ 每個(gè)點(diǎn)連向 $4$，權(quán)值為 $10$，操作如下所示：

即，將區(qū)間 $1～2$ 和 $3～3$ 連向 $4$ 即可，不過(guò)此時(shí)發(fā)現(xiàn)，圖中為有向圖，而現(xiàn)在是無(wú)向圖所以我們要對(duì)于圖中的每一條邊標(biāo)記方向和權(quán)值（這里線段樹(shù)就是一張圖，葉子節(jié)點(diǎn)就是我們的 $1～n$ 節(jié)點(diǎn)）

其中，為何線段樹(shù)上的邊方向都為向父親節(jié)點(diǎn)？那是因?yàn)?$1$，$2$ 號(hào)點(diǎn)只有這樣才能順著邊走到 $4$ 號(hào)節(jié)點(diǎn)，對(duì)于為何權(quán)值設(shè)為 $0$，因?yàn)檫@是 $1$ 條虛邊（不存在的），不能對(duì)最短路做出任何貢獻(xiàn)。

不過(guò)，上文是區(qū)間連節(jié)點(diǎn)，當(dāng)是節(jié)點(diǎn)連區(qū)間的時(shí)候（操作 $3$）邊都是正好反著的，所以再建 $1$ 棵線段樹(shù)即可（不過(guò)沒(méi)必要真的去再建 $1$ 棵，具體見(jiàn)代碼）文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-830504.html

C o d e Code Code

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

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int SIZE = 4e6 + 10, SIZE2 = 1e6 + 10;

int N, Q, S;
int h[SIZE2], e[SIZE], ne[SIZE], w[SIZE], idx;
int Id[2], Dist[SIZE2], Vis[SIZE2];
struct Segment
{
	int l, r;
	int L, R;
}Tree[SIZE2 << 2];

void add(int a, int b, int c)
{
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int Build(int l, int r, int Sd, int k)
{
	if (l == r)
	{
		Tree[l] = {l, l};
		return l;
	}
	int P = ++ Id[k];
	Tree[P] = {l, r};

	int mid = l + r >> 1;
	Tree[P].L = Build(l, mid, Sd, k), Tree[P].R = Build(mid + 1, r, Sd, k);

	if (!Sd) add(Tree[P].L, P, 0), add(Tree[P].R, P, 0);
	else add(P, Tree[P].L, 0), add(P, Tree[P].R, 0);

	return P;
}

void Add(int u, int l, int r, int p, int w, int Sd)
{
	if (Tree[u].l >= l && Tree[u].r <= r)
	{
		if (!Sd) add(u, p, w);
		else add(p, u, w);
		return;
	}

	int mid = Tree[u].l + Tree[u].r >> 1;
	if (mid >= l) Add(Tree[u].L, l, r, p, w, Sd);
	if (mid < r) Add(Tree[u].R, l, r, p, w, Sd);
}

void Dijkstra(int S)
{
	memset(Dist, 0x3f, sizeof Dist);
	memset(Vis, 0, sizeof Vis);
	priority_queue<PII, vector<PII>, greater<PII>> Heap;
	Heap.push({0, S}), Dist[S] = 0;

	while (Heap.size())
	{
		auto Tmp = Heap.top();
		Heap.pop();

		int u = Tmp.second;
		if (Vis[u]) continue;
		Vis[u] = 1;

		for (int i = h[u]; ~i; i = ne[i])
		{
			int j = e[i];
			if (Dist[j] > Dist[u] + w[i])
			{
				Dist[j] = Dist[u] + w[i];
				Heap.push({Dist[j], j});
			}
		}
	}
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	memset(h, -1, sizeof h);

	cin >> N >> Q >> S;

	if (N == 1)
	{
		cout << 0 << endl;
		return 0;
	}

	Id[0] = N;
	Build(1, N, 0, 0);
	Id[1] = Id[0];
	Build(1, N, 1, 1);

	while (Q --)
	{
		int Op, v, u, l, r, w;
		cin >> Op >> u;

		if (Op == 1)
		{
			cin >> v >> w;
			add(u, v, w);
		}
		else if (Op == 2)
		{
			cin >> l >> r >> w;
			Add(Id[0] + 1, l, r, u, w, 1);
		}
		else
		{
			cin >> l >> r >> w;
			Add(N + 1, l, r, u, w, 0);
		}
	}

	Dijkstra(S);

	for (int i = 1; i <= N; i ++)
		if (Dist[i] >= 1e18) cout << -1 << " ";
		else cout << Dist[i] << " ";

	return 0;
}

到了這里，關(guān)于【圖論經(jīng)典題目講解】CF786B - Legacy 一道線段樹(shù)優(yōu)化建圖的經(jīng)典題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！