题解：P12332 [蓝桥杯 2023 省 Java B] 魔法阵

题目传送门

观察到

k

极小，所以你直接考虑对原图建分层图。考虑再分层图上的两种转移（设层数

i\in [0,k]

）：

这条边没选，需要满足 $i=0$ 或 $i=k$ ，那么直接在第 $i$ 层图转移。转移时边权按原边权算。
这条边选了，需要满足 $i<k$ ，那么从第 $i$ 层图转移到第 $i+1$ 层图，转移时边权按 $0$ 算。

答案即为

\min(f_{n-1,0},f_{n-1,k})

。

实际上只需要在松弛更新的时候考虑这两种转移即可，根本不需要把分层图建出来。直接硬跑 dij 或 ~~已死算法~~spfa 都能过。

CPP

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define mkp make_pair
#define pi pair<int, int>
typedef long long ll;
const int N = 1e3 + 10, K = 11;
int f[N][K], inf = 1e9, n, m, k;
queue<pi> q;
vector<pi> g[N];
bool inque[N][K];
il void spfa(int s)
{
	for(int i = 0;i < n;++i)
		for(int j = 0;j <= k;++j)
			f[i][j] = inf;
	f[s][0] = 0;
	inque[s][0] = 1;
	q.push(mkp(s, 0));
	while(q.size())
	{
		pi cur = q.front();
		q.pop();
		int u = cur.first, j = cur.second;
		inque[u][j] = 0;
		for(auto vv : g[u])
		{
			int v = vv.first, w = vv.second;
			if((j == 0 || j == k) && f[v][j] > f[u][j] + w)
			{
				f[v][j] = f[u][j] + w;
				if(!inque[v][j])
				{
					q.push(mkp(v, j));
					inque[v][j] = 1;
				}
			}
			if(j < k && f[v][j + 1] > f[u][j])
			{
				f[v][j + 1] = f[u][j];
				if(!inque[v][j + 1])
				{
					q.push(mkp(v, j + 1));
					inque[v][j + 1] = 1;
				}
			}
		}
	}
}
int main()
{
	cin >> n >> k >> m;
	while(m--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back(mkp(v, w));
		g[v].push_back(mkp(u, w));
	}
	spfa(0);
	cout << min(f[n - 1][0], f[n - 1][k]);
	return 0;
}

题解：P12332 [蓝桥杯 2023 省 Java B] 魔法阵

文章操作

题目传送门

相关推荐

评论

题解：P12332 [蓝桥杯 2023 省 Java B] 魔法阵