当前位置：首页 > article >正文

洛谷 P1186 玛丽卡（最短路，并查集，线段树）

article 2024/10/25 0:23:05

题目链接

https://www.luogu.com.cn/problem/P1186

思路

因为边的数量 $\le n \times (n-1) / 2$ ，所以使用朴素Dijkstra更优。

我们先用Dijkstra求出 $1$ 号点到 $n$ 的最短路径。

我们枚举不在最短路径上的边，规定它是删除最短路径某一段后必定会走的边。这时我们只要找到该边替换的最短路径上的那一段路径，我们便可以知道删掉哪些边之后，最短路径会更新成经过该边的最短路径的距离，最后求一下最大值即可。

对于如何找到最短路径上被替换的那一段路径，我们可以考虑使用并查集来维护。我们规定每一个点的父亲为最短路上的前驱，最短路径上的点的父亲规定为自己（即最短路径上的点为祖先）。

线段树维护区间最大值：因为我们要替换的最短路径上的那一段路径必然是连续的，因此我们可以将最短路径上的边视为点，整条路径相当于一个区间。因此我们可以用线段树来维护区间最大值。

时间复杂度： $O(n^{2}log_{2}n)$

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e3 + 5, M = 1e4 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, m, ans;
int dist1[N], distn[N], pre[N], f[N], pos[N], cnt;
bool st[N];
int mp[N][N];
int find(int x)
{
	if (x != f[x])
		f[x] = find(f[x]);
	return f[x];
}
void dijkstra(int s, int d[])
{
	fill(d + 1, d + n + 1, inf);
	fill(st + 1, st + n + 1, false);
	d[s] = 0;
	for (int i = 1; i <= n; i++)
	{
		int t = -1;
		for (int j = 1; j <= n; j++)
		{
			if (!st[j] && (t == -1 || d[t] > d[j])) t = j;
		}
		st[t] = true;
		for (int j = 1; j <= n; j++)
		{
			if (d[j] > d[t] + mp[t][j])
			{
				d[j] = d[t] + mp[t][j];
				if (s == 1) pre[j] = t;
			}
		}
	}
}
struct segmenttree
{
	struct node
	{
		int l, r, maxx;
	};
	vector<node>tree;

	segmenttree(): tree(1) {}
	segmenttree(int n): tree(n * 4 + 1) {}

	void pushup(int u)
	{
		auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];
		root.maxx = max(left.maxx, right.maxx);
	}

	void pushdown(int u)
	{
		auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];
		left.maxx = min(left.maxx, root.maxx);
		right.maxx = min(right.maxx, root.maxx);
	}

	void build(int u, int l, int r)
	{
		auto &root = tree[u];
		root = {l, r};
		if (l == r)
		{
			root.maxx = inf;
		}
		else
		{
			int mid = l + r >> 1;
			build(u << 1, l, mid);
			build(u << 1 | 1, mid + 1, r);
			pushup(u);
		}
	}

	void modify(int u, int l, int r, int val)
	{
		auto &root = tree[u];
		if (root.l >= l && root.r <= r)
		{
			root.maxx = min(root.maxx, val);
			return;
		}
		pushdown(u);
		int mid = root.l + root.r >> 1;
		if (l <= mid) modify(u << 1, l, r, val);
		if (r > mid) modify(u << 1 | 1, l, r, val);
		pushup(u);
	}

	int query(int u, int l, int r)
	{
		auto &root = tree[u];
		if (root.l >= l && root.r <= r)
		{
			return root.maxx;
		}
		pushdown(u);
		int mid = root.l + root.r >> 1;
		int res = -inf;
		if (l <= mid) res = query(u << 1, l, r);
		if (r > mid) res = max(res, query(u << 1 | 1, l, r));
		return res;
	}
};
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		fill(mp[i] + 1, mp[i] + n + 1, inf);
	for (int i = 1, u, v, w; i <= m; i++)
	{
		cin >> u >> v >> w;
		mp[u][v] = mp[v][u] = w;
	}
	dijkstra(1, dist1);
	dijkstra(n, distn);
	for (int i = 1; i <= n; i++)
		f[i] = pre[i];
	for (int i = n; i; i = pre[i])
	{
		pos[i] = ++cnt;//把路径抽象成区间上的点
		f[i] = i;
		if (pre[i])
		{
			mp[i][pre[i]] = mp[pre[i]][i] = inf;
		}
	}

	segmenttree smt(n);
	smt.build(1, 1, cnt);

	for (int i = 1, u, v, w; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			if (mp[i][j] == inf) continue;
			u = pos[find(i)];
			v = pos[find(j)];
			if (u == v) continue;
			if (u > v) swap(u, v);
			w = min(dist1[i] + mp[i][j] + distn[j], distn[i] + mp[i][j] + dist1[j]);
			smt.modify(1, u + 1, v, w);
		}
	}
	int ans = smt.query(1, 2, cnt);
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	// cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}