# A*

Acwing178 第K短路

原题链接:Acwing178

题目大意:给定一张 N 个点(编号 1,2…N ),M 条边的有向图,求从起点 S 到终点 T 的第 K 短路的长度,路径允许重复经过点或边。

注意: 每条最短路中至少要包含一条边。

……

READ MORE

Acwing179 八数码

原题链接:Acwing179

题目大意:在一个3×3的网格中,1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。

例如:

1 2 3
X 4 6
7 5 8

在游戏过程中,可以把“X”与其上、下、左、右四个方向之一的数字交换(如果存在)。

我们的目的是通过交换,使得网格变为如下排列(称为正确排列):

1 2 3
4 5 6
7 8 X
……

READ MORE