在失落的遗迹深处，考古学家发现了一组由 块巨大符文石组成的古代能量传导系统。 这些符文石从左至右线性排列，编号从 到 。每块符文石上都铭刻着若干个能量铭文，其数字编号从 到 不等且不重复。 能量可以在系统中通过两种方式流动： 1. 内部灵脉 (Internal Ley Line) ：连接同一块符文石上任意两个铭文的能量通路。 2. 能量桥 (Energy Bridge) ：连接相邻两块符文石（即符文石 与 ）上特定铭文的能量通路。 如今，一部分古老的内部灵脉和能量桥仍然存在。您的任务是找到一条“最和谐”的激活路径，将能量从符文石 顺次引导至符文石 。 一条完整的激活路径，在每一块符文石 () 上，都会选定一个输入铭文和一个输出铭文。 能量通过能量桥从符文石 的输出铭文流入符文石 的输入铭文，然后在石头内部通过一条灵脉，从输入铭文流向输出铭文，最终再通过能量桥流向下一块符文石。 - 对于起始符文石 ，路径从其某个输入铭文开始。 - 对于终止符文石 ，路径在其某个输出铭文结束。 ## 激活约束 1. 符文石的数量 满足：。 2. 每块符文石上的最大铭文编号 满足：。 3. 除了起始和终止铭文外，路径上所有被选中的铭文都必须一端连接内部灵脉，另一端连接能量桥。 4. 古老的**能量桥**是固定不变的，您不能修改或增加新的能量桥。 5. 古老的**内部灵脉**是神圣的，您不能修改它们，但可以在任意两个未被占用的铭文之间开辟新的灵脉。 ## 和谐度评定标准 “最和谐”的路径并非由单一数值决定，而是一种基于字典序的比较： 1. 逐石比较原则： 比较两条不同的激活路径时，将从符文石 开始逐一对比它们的“和谐度”。一旦在第 块符文石上分出优劣，则该路径的整体和谐度即被确定，无需再比较后续的符文石。 2. 单石和谐度 (优先级由高到低): 对于任意一块符文石，其激活方式的和谐度按以下三条规则评定： - 规则一 (尊重先古) ：优先选择利用已存在的古代灵脉进行连接的方案。 - 规则二 (最小扰动) ：在规则一判定相同（均为已存在或均为新建）时，优先选择输入与输出铭文编号之和更小的方案。 - 规则三 (稳定输入) ：若上述两项均相同，则优先选择输入铭文编号更小的方案。 形式化说明：对第 i 块符文石（输入铭文为 p_in，输出铭文为 p_out），定义评分三元组 (is_new, p_in + p_out, p_in)，其中 is_new∈{0,1}，已存在灵脉取 0，新建灵脉取 1。 两条路径的比较按从左到右逐石进行，遇到首个评分三元组字典序更小者即为整体更优。
输入描述:
输入的第一行为一个整数 ，代表符文石的总数。随后，对于第 块符文石，输入遵循以下格式：1. 第 块符文石上的所有铭文编号列表（以空格分隔）。2. 第 块符文石上已存在的内部灵脉列表。每条灵脉表示为 `铭文A-铭文B`。若不存在，则为一行 `0`。3. (对于 ) 连接第 块和第 块符文石的能量桥列表。每条能量桥表示为 `石头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
示例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 整理上传
加载中...