分层图

Carousel / 2023-08-25 / 原文

引入：P4822

我们可以建出一个 \(k + 1\) 层的图，第 \(i\) 层指的是使用了 \(i - 1\) 次的 SpellCard。

每一层的一个点到每一层的另一个按照正常的方式连就行了。

另一种情况就是层与层的连边，也就是使用 SpellCard。

假如说有一条起点为 \(u\) 终点为 \(v\) 长度为 \(w\) 的边。

于是我们按照题意就知道从第 \(i\) 层的 \(u\) 连到第 \(i + 1\) 层的 \(v\) 可以连一条长度为 \(w \div 2\)。

同理从第 \(i\) 层的 \(v\) 连到第 \(i + 1\) 层的 \(u\) 可以连一条长度为 \(w \div 2\)。但是这两条边都是有向边。

这样这题的边就连完了，直接从第 \(1\) 层的 \(1\) 号点开始跑最短路，答案就是 \(min(dis_{n \times i})\) 其中 \(1 \le i \le k + 1\)。

附上主函数的代码：

int main()
{
	cin >> n >> m >> k;
	for(int i = 1;i <= m;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		for(int j = 1;j <= k + 1;j++)
		{
			add_edge(t(u,j),t(v,j),w);
			add_edge(t(v,j),t(u,j),w);
			add_edge(t(u,j),t(v,j + 1),w / 2);
			add_edge(t(v,j),t(u,j + 1),w / 2);
		}
	}
	dij();
	int ans = 1e9;
	for(int i = 1;i <= k + 1;i++)
	{
		ans = min(ans,dis[n * i]);
		// cout << dis[n * i] << '\n';
	}
	cout << ans;
	return 0;
}

然后再给大家两道练习题：P4568,P2939