Tag: dijkstra

2 篇文章

Luogu P2446 [SDOI2010]大陆争霸 题解
Description 题目链接 $m$条单向边连接$n$个城市,通过每边要$w_i$​单位时间。从$1$开始,依次摧毁城市,仅仅摧毁不用时间,直到摧毁$n$结束。部分城市被别的城市保护,只有保护它的城市被摧毁后,才能摧毁这个城市。求结束的最短时间。 Solution 把所有保护关系从保护者连向被保护者一条边,每一次遍历到一个点时,把所有与该点有关…
Luogu P4366 [Code+#4]最短路 题解
Description 题目链接 给定一张 $N$ 个点的图,$M$ 条边,另外任意两个点之间还有一条权值为 $(i \oplus j) \times C$ 的边,问 $A$ 到 $B$ 的最短路。 $1\leq N \leq 10^5,1\leq M \leq 5\times 10^5$ Solution 首先,暴力建图肯定是不行的,$…