专栏文章

题解：P14307 【MX-J27-T4】点灯

wwoshi_dabian
P14307题解参与者 14已保存评论 20

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
20 条
当前快照
1 份
快照标识符
@mini13d1
此快照首次捕获于
2025/12/02 02:44
3 个月前
此快照最后确认于
2025/12/02 02:44
3 个月前
查看原文
update 2025/10/26 接受了大佬们的建议，将新渲染框设置为默认打开（代码框除外）。并给每一层添加了清晰概括便于学习。
注：本题解有层层剖析部分，在总结中也有传统题解风格，可以自由选择。由于本题是典型的分层图最短路题，故讲解详细，适于新手初学分层图。
让我们一层一层剥开这道题！

零楼：读懂题目

题意解析
给定一个 nn 个点 mm 条边的无向图，每条边有一个限制 ww，代表在经过该边后路径长度达到 ww 才能使用该边。以 11 为起点，是否存在一个长度 dd，使得起点到每个点都有一条长度为 dd 的路径。求最小的 dd。

一楼：解题方向

问
怎样判断起点到一个点是否存在长度为 dd 的路径？
答
如果存在一条长度为 d′d' 的路径。满足：d≡d′(mod  2)d\equiv d'(\mod 2) 且 d′<dd'<d。则长度为 d′d' 的路径可以通过在途中 回退一条边再回来 使得路径长度增加 22，并重复该操作直至与 dd 相等。所以我们可以分别找到起点到每个点 长度为偶数的最短路和长度为奇数的最短路。

二楼：分层图的引入

问
如何分别求出奇偶最短路？怎样处理边的限制？
答1
我们引入分层图。定义 disi,0dis_{i,0} 表示起点到 ii 点长度为偶数的最短路，disi,1dis_{i,1} 为长度为奇数的最短路。跑最短路的过程与常规写法无异。只是在找到一条到达点 vv 且长度为 ww 的路径时，我们需要更新的是 disv,wmod  2dis_{v,w\mod2}。
答2
既然限制未到，那么我们只需要和一楼采取同样操作：回退再回来，直到满足限制。
分层图示例代码
我选用了 dijkstra 的写法，不过这题 spfa 应该也不会被卡常。
CPP
		Q.push((node1){1, 0});
		while (Q.size()) {
			t = Q.top();
			Q.pop();
			tu = t.u;
			tw = t.w;
			if (book[tu][tw % 2]) continue;
			book[tu][tw % 2] = 1;
			for (int i = 0; i < V[tu].size(); i++) {
				tw = t.w;
				tv = V[tu][i].v;
				if (tw < V[tu][i].w) {
					tw += ((V[tu][i].w - tw) / 2) * 2;
					if (tw < V[tu][i].w) tw += 2;
				}
				tw++;
				if (dis[tv][tw % 2] > tw) {
					dis[tv][tw % 2] = tw;
					Q.push((node1){tv, tw, tw % 2});
				}
			}
		}

三楼：答案获取

问
在获得奇偶最短路后，如何利用其找出答案？
答
只需要分别统计到达各个点奇数最短路中的最大值和偶数最短路中的最大值，再在二者中取最小值。
原因在一楼有讲，通过回退再回来使长度和最长路径一样。而最长路径就是满足各个点通过回退能到达的最小值。

四楼：无解判断

问
什么情况下会无解？
答
常规情况是奇数最短路和偶数最短路中都存在无法到达的点，因此无解。
特殊情况是由于起点开始时无法回退，若与起点相连的每一条边天数限制都大于 11，那么将无法迈出第一步，无解。

跳楼：AC此题

总结
核心算法：分层图最短路。由于到达每个点可以通过路途中回退再回来使得路径长度增加 22，所以分别求出长度为奇数和长度为偶数的最短路。只要奇偶性相同，较短路径就一定能凑出较长路径，因此对最短路求最大值更新答案。
完整代码CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2.5e4 + 10;
struct node{
	ll v, w;
};
vector<node> V[N];
ll dis[N][2], book[N][2];
struct node1{
	ll u, w, op;
	bool operator<(const node1 x) const{
		return w > x.w;
	}
};
priority_queue<node1> Q;
int main() {
	ll c, T;
	scanf("%lld%lld", &c, &T);
	ll n, m, o, u, v, w;
	node1 t;
	ll tu, tv, tw, ans, minn, flag;
	while (T--) {
        scanf("%lld%lld%lld", &n, &m, &o);
		for (int i = 1; i <= n; i++) V[i].clear();
		flag = 0;
		for (int i = 1; i <= m; i++) {
        scanf("%lld%lld%lld", &u, &v, &w);
			w--;
			if ((u == 1 || v == 1) && w == 0) flag = 1;
			V[u].push_back((node){v, w});
			V[v].push_back((node){u, w});
		}
		if (!flag) {
            printf("-1\n");
			continue;
		}
		for (int i = 1; i <= n; i++) dis[i][0] = 0x7fffffffll * 100, dis[i][1] = 0x7fffffffll * 100;
		for (int i = 1; i <= n; i++) book[i][0] = 0, book[i][1] = 0;
		dis[1][0] = 0;
		Q.push((node1){1, 0});
		while (Q.size()) {
			t = Q.top();
			Q.pop();
			tu = t.u;
			tw = t.w;
			if (book[tu][tw % 2]) continue;
			book[tu][tw % 2] = 1;
			for (int i = 0; i < V[tu].size(); i++) {
				tw = t.w;
				tv = V[tu][i].v;
				if (tw < V[tu][i].w) {
					tw += ((V[tu][i].w - tw) / 2) * 2;
					if (tw < V[tu][i].w) tw += 2;
				}
				tw++;
				if (dis[tv][tw % 2] > tw) {
					dis[tv][tw % 2] = tw;
					Q.push((node1){tv, tw, tw % 2});
				}
			}
		}
		ans = 0x7fffffffll * 100, minn = -0x7fffffffll * 100;
		for (int i = 1; i <= n; i++) minn = max(minn, dis[i][0]);
		ans = min(ans, minn);
		minn = -0x7fffffffll * 100;
		for (int i = 1; i <= n; i++) minn = max(minn, dis[i][1]);
		ans = min(ans, minn);
		if (ans != 0x7fffffffll * 100) printf("%lld\n", ans * o);
		else printf("-1\n");
	}
	return 0;
}

评论

共 20 条评论，欢迎与作者交流。

正在加载评论...