首页 > 试题广场 >

古代符文路径的激活

[编程题]古代符文路径的激活
  • 热度指数:30 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
在失落的遗迹深处,考古学家发现了一组由 N 块巨大符文石组成的古代能量传导系统。
这些符文石从左至右线性排列,编号从 1N。每块符文石上都铭刻着若干个能量铭文,其数字编号从 1M 不等且不重复。

能量可以在系统中通过两种方式流动:

1. 内部灵脉 (Internal Ley Line) :连接同一块符文石上任意两个铭文的能量通路。
2. 能量桥 (Energy Bridge) :连接相邻两块符文石(即符文石 ii+1)上特定铭文的能量通路。

如今,一部分古老的内部灵脉和能量桥仍然存在。您的任务是找到一条“最和谐”的激活路径,将能量从符文石 1 顺次引导至符文石 N

一条完整的激活路径,在每一块符文石 i (1 < i < N) 上,都会选定一个输入铭文和一个输出铭文
能量通过能量桥从符文石 i-1 的输出铭文流入符文石 i 的输入铭文,然后在石头内部通过一条灵脉,从输入铭文流向输出铭文,最终再通过能量桥流向下一块符文石。

- 对于起始符文石 1,路径从其某个输入铭文开始。
- 对于终止符文石 N,路径在其某个输出铭文结束。

## 激活约束

1. 符文石的数量 N 满足:1 < N < 20
2. 每块符文石上的最大铭文编号 M 满足:1 < M < 100
3. 除了起始和终止铭文外,路径上所有被选中的铭文都必须一端连接内部灵脉,另一端连接能量桥。
4. 古老的**能量桥**是固定不变的,您不能修改或增加新的能量桥。
5. 古老的**内部灵脉**是神圣的,您不能修改它们,但可以在任意两个未被占用的铭文之间开辟新的灵脉。

## 和谐度评定标准

“最和谐”的路径并非由单一数值决定,而是一种基于字典序的比较:

1. 逐石比较原则
比较两条不同的激活路径时,将从符文石 1 开始逐一对比它们的“和谐度”。一旦在第 i 块符文石上分出优劣,则该路径的整体和谐度即被确定,无需再比较后续的符文石。

2. 单石和谐度 (优先级由高到低):
对于任意一块符文石,其激活方式的和谐度按以下三条规则评定:
- 规则一 (尊重先古) :优先选择利用已存在的古代灵脉进行连接的方案。
- 规则二 (最小扰动) :在规则一判定相同(均为已存在或均为新建)时,优先选择输入与输出铭文编号之和更小的方案。
- 规则三 (稳定输入) :若上述两项均相同,则优先选择输入铭文编号更小的方案。

形式化说明:对第 i 块符文石(输入铭文为 p_in,输出铭文为 p_out),定义评分三元组 (is_new, p_in + p_out, p_in),其中 is_new∈{0,1},已存在灵脉取 0,新建灵脉取 1。
两条路径的比较按从左到右逐石进行,遇到首个评分三元组字典序更小者即为整体更优。


输入描述:
输入的第一行为一个整数 N,代表符文石的总数。

随后,对于第 i=1, \dots, N 块符文石,输入遵循以下格式:

1. 第 i 块符文石上的所有铭文编号列表(以空格分隔)。
2. 第 i 块符文石上已存在的内部灵脉列表。每条灵脉表示为 `铭文A-铭文B`。若不存在,则为一行 `0`。
3. (对于 i < N) 连接第 i 块和第 i+1 块符文石的能量桥列表。每条能量桥表示为 `石头i的铭文-石头i+1的铭文`。若不存在,则为一行 `0`。


输出描述:
输出一行由空格分隔的数字,代表“最和谐”激活路径所经过的**所有铭文**编号序列。

如果不存在任何一条能从头贯穿至尾的完整激活路径,则输出 `-1`。
示例1

输入

3
1 2 3
0
2-1
1 2 3 4
3-4
1-2
1 2 3 4 5
1-5

输出

-1
示例2

输入

15
4 5 6 7 8 9 10 12 13 17 18 20 21 25 27 29 30 32 33 34 36 37 38 39 40 42 43 44 47 48 49 50 52 54 55 57 58 59 60 61 62 64 65 66 67 69 71 74 75 77 79 80
29-66
62-16 18-23
1 5 12 13 15 16 20 21 23 27 31 32 33 34 37 38 39 43 44 45 50 54 55 57 59 60 65 67 68 71 74 76 79
5-57 50-79
27-2 45-12
2 3 4 6 8 10 11 12 14 16 17 21 26 28 30 31 35 37 39 40 42 44 45 47 49 51 52 53 55 57 63 67 68 70 71 77 80
39-57 3-10 16-37 35-47 8-28
17-76 2-76 10-70 53-31 51-29
1 2 3 4 6 7 10 11 15 16 17 20 21 22 23 25 28 29 31 33 36 39 40 41 42 45 46 49 50 51 52 54 55 57 59 61 63 64 66 69 70 71 73 76 80
40-66 31-46
45-17 76-35 54-3 41-36
1 2 3 4 5 11 12 16 17 18 19 20 21 22 24 26 29 30 31 35 36 40 42 44 47 50 51 52 53 54 56 57 62 63 64 66 70 71 72 74 75 77 78 79
36-77 63-77 2-5 36-71 18-57
63-68 5-34 74-34
2 5 8 10 12 17 18 19 20 21 22 34 35 36 37 39 41 44 51 54 56 60 62 67 68 69 73 74 75 77
0
56-35 8-43 60-46 39-45 62-63
7 9 11 15 23 26 35 37 39 41 43 45 46 47 52 55 57 59 63 64 66 68 73 74 76 77
35-59 26-68
39-38 66-11
4 6 9 11 12 16 18 20 24 26 34 35 37 38 45 49 51 56 57 61 63 64 66 67 68 71 73
4-9 12-61 63-71 16-20
34-73 56-21
1 2 3 6 7 10 13 18 19 21 22 23 25 28 31 32 33 34 35 37 39 41 42 46 48 50 51 53 55 58 61 62 66 67 68 69 72 73 74 75 76
18-58
22-1 19-64 76-5 46-4 50-65
1 4 5 6 8 11 13 14 15 19 20 21 22 23 24 26 27 28 29 32 34 36 39 41 45 46 48 51 52 53 55 59 60 64 65 67 68 69 70 72 76 77 80
14-70 14-28 32-60 6-15
27-52 13-19 45-44 23-73 68-62
4 5 6 7 10 14 15 19 20 21 25 29 32 34 35 37 39 44 49 50 52 61 62 65 69 70 73 74 78 79
15-61 50-69 35-44 25-50
44-35 52-46 4-21
1 3 4 12 14 15 17 18 21 25 26 27 31 32 33 35 37 40 46 47 49 50 51 55 56 60 61 62 66 68 69 70 72 74 76 79 80
21-80 12-69 1-69 21-69 18-47
17-60
1 7 8 11 13 16 17 18 20 21 26 34 35 38 39 43 44 45 46 47 48 50 54 55 56 57 58 60 62 63 64 65 66 67 71 72 74 76 78 79
8-46 35-72
76-15 72-5 47-14 55-30 79-43
1 3 4 5 7 9 12 14 15 16 19 21 26 28 29 30 32 34 37 41 43 47 48 50 53 54 56 65 66 71 72 73 74 75 77 78
21-48 9-30 16-65
29-11 1-12 43-26
2 3 5 6 7 9 11 12 13 23 24 25 26 28 33 37 38 39 44 48 51 52 54 57 58 59 60 62 64 68 69 72 73 75 76 77 78 79
69-78 3-52 26-77 9-75

输出

4 18 23 27 2 17 76 45 17 74 34 8 43 39 38 34 73 19 64 13 19 52 46 17 60 47 14 1 12 2

备注:
本题由牛友@Charles 整理上传
这个题目输出-1能直接骗0.7分
发表于 今天 11:11:09 回复(0)
看了5分钟,我连题目都没看懂
发表于 2025-09-15 18:52:59 回复(0)