题目描述

Fritz 造了一台小机器。它有点像现代计算机，但它的全部内存只由若干个整型栈组成。

栈是一种只允许访问最上方元素的数据结构。你可以：

• 读取顶部元素；
• 修改顶部元素；
• 删除顶部元素；
• 或在顶部压入一个新元素。

删除顶部元素称为 pop，在顶部加入新元素称为 push。

为了控制这台机器，Fritz 设计了一门编程语言，叫做 Stacklang。一段 Stacklang 程序由若干条指令组成，每条指令可以带参数。比如：

• pop S：从栈 S 弹出一个元素；
• push S 10：向栈 S 压入整数 10。

此外语言还支持：

• 算术运算；
• 控制流（if 与 goto）；
• 输入输出；
• 简单注释。

现在 Fritz 想用这台机器来解决一个经典问题：

在一个有向图中，边权只可能为 0 或 1，求给定起点到终点的最短路径长度；如果不存在路径，则输出 -1。

你需要编写一个名为 stacklang.txt 的 Stacklang 程序，完成该任务。

本题类型

这是一道提交程序文件题。你需要提交的是一份 Stacklang 程序，而不是通常意义上的 C/C++/Python 源码。

本地解释器输入格式

为方便本地测试，题目提供了解释器。解释器输入格式如下：

第一行输入两个整数 N, M，表示图的顶点数和边数。
第二行输入两个整数 Start, End，表示起点与终点。
接下来 M 行，每行三个整数 From_i, To_i, Len_i，表示一条有向边以及其边权。
之后继续输入你的 Stacklang 程序，直到文件结束。

程序格式说明

程序中的排版并不重要（可以有缩进等），但所有 token（指令、栈名、注释分隔符等）必须由空格、换行或其他空白字符分隔。

注释用 # 包围，例如：

code # comment # code

程序读取到文件结束为止。

指令说明

设：

• I 表示一条指令；
• C 表示一个条件；
• Z 表示一个整数；
• S 表示一个栈；
• L 表示一个标签；
• R 表示“一个整数 Z 或一个栈 S”；
• top(S) 表示栈 S 的栈顶元素；
• top(Z) 就是常数 Z 本身。

类型	形式	含义
I	alloc Z S1 S2 ... SZ	分配 Z 个栈，名字分别为 S1, S2, ..., SZ
	pop S	从 S 弹出一个元素
	push S R	把 top(R) 压入 S
	add S R	top(S) := top(S) + top(R)
	sub S R	top(S) := top(S) - top(R)
	print R	在本地解释器中打印 top(R)；在评测机上无效果
	return R	返回 top(R)，即程序输出结果
	getStart S	将起点压入 S
	getEnd S	将终点压入 S
	getEdges S R	将从顶点 top(R) 出发的所有边压入 S
	label L	在当前位置定义标签 L
	goto L	跳转到标签 L
	if C goto L	若条件 C 为真则跳转到 L
C	empty S	当 S 为空时为真
	notEmpty S	当 S 非空时为真
	equal R1 R2	当 top(R1) = top(R2) 时为真
	notEqual R1 R2	当 top(R1) != top(R2) 时为真

关于 get 系列指令的重要说明

所有 get 指令在第一次对某个对象调用时才会压入相应数据；之后若再次对同一个对象调用，则不会重复压入。

尤其是：

• 若对同一个顶点多次执行 getEdges，只有第一次会把边压入栈；
• 若对不同顶点执行 getEdges，则依然会正常工作。

另外，getEdges 压入数据的顺序如下：

• 所有边权为 1 的边先压入；
• 所有边权为 0 的边后压入；
• 对于每条边，先压入它的权值，再压入它指向的顶点。

也就是说，若从顶点 u 出发有若干条边，那么压入栈顶后的内容形如：

1, v1, ..., 1, vt, 0, v_{t+1}, ..., 0, v_{t+p}

其中这些 v_i 是 u 的所有出边终点，前 t 条边权为 1，后 p 条边权为 0。

其他说明

• 对空栈取 top(S) 属于错误；
• 对非法顶点调用 getEdges 属于错误；
• 使用未定义（未 alloc 或未 label）的栈或标签属于错误；
• 栈中整数范围与 C++ 的 int 相同；溢出时行为与 C++ 相同；
• 栈名和标签名必须是合法 C++ 标识符，且不能与指令名重复；
• 常数可以是负数。

评测与得分

若你的程序：

• 运行时不出现任何错误；
• 分配的栈数不超过 10；
• 在 10^7 次迭代内返回正确答案；

则该测试通过。

每个子任务的得分取决于：

• 使用的栈数；
• 以及（在某些情况下）使用的最大迭代次数。

子任务	分值	限制
1	20	所有边权都为 0
2		从任意顶点到任意顶点的路径至多一条
3	30	所有边权都为 1
4		无额外限制

栈数	迭代次数	得分比例
<= 2	<= 3 × 10^6	100%
	> 3 × 10^6	90%
3	不限	70%
4		50%
5		40%
>= 6		30%

注意：由于最终成绩按各子任务的最好提交分别计算，因此对不同子任务分别提交不同程序是有意义的。

图的数据范围

1 <= N <= 2 × 10^4
0 <= M <= 5 × 10^4
0 <= Start, End, From_i, To_i < N
0 <= W_i <= 1

允许：

• 自环；
• 重边；
• Start = End。

示例图 1

4 7
0 2
0 1 1
1 1 1
0 3 0
2 0 0
0 3 1
3 1 0
1 2 1

对应答案：

1

示例图 2

3 2
1 0
0 2 1
2 1 0

对应答案：

-1

示例说明

在第一个图中，从 0 到 2 的最短路是：

• 0 -> 3，边权 0；
• 3 -> 1，边权 0；
• 1 -> 2，边权 1；

因此最短距离为 1。

第二个图中，从 1 到 0 不存在路径，因此答案为 -1。

示例程序

alloc 4 start end edges cnt
getStart start
getEnd end

push cnt 0
getEdges edges start
getEdges edges end

label edgesLoop
if empty edges goto exitEdgesLoop
  add cnt 1
  pop edges # don't need len #
  print edges
  pop edges
  goto edgesLoop
label exitEdgesLoop

# cnt needs to be doubled when
# start and end are equal #
if notEqual start end goto finish
  add cnt cnt
label finish
return cnt

原题说明：上面的程序并不能解决本题。它只是计算：

• 从 Start 出发的边数；
• 加上从 End 出发的边数；

若 Start = End，则由于第二次 getEdges edges end 不会压入任何内容，所以程序通过 add cnt cnt 手动把计数翻倍。

程序还会打印所有从 Start 或 End 出发的边所指向的顶点；这种打印在正式评测中不会生效。