Stacklang Shortest Paths
National Olympiad — National round (2021 season)
Submission name: stacklang.cpp
Problem summary
Write stacklang.txt, a program in the supplied stack language, that returns the shortest directed 0–1 path distance or −1. Each vertex’s outgoing edges can be fetched only once. The score also depends on allocated stacks and instruction count.
Input
The contest artifact is Stacklang source. The local interpreter reads N M, Start End, M lines From To Len, then the Stacklang program through EOF.
Output
The program must execute return distance, or return −1 for an unreachable goal.
Constraints
N ≤ 20000; M ≤ 50000; 0-based vertices; weights 0 or 1; self-loops and repeated edges allowed; at most 10 stacks and 10000000 executed instructions.
Worked example
Example input contains the graph only; append generated Stacklang source when using the supplied interpreter. Output is the returned result, not the generator stdout.
Input
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
Output
1
Solution analysis
- The C++ listing is an offline generator for the actual Stacklang submission, not an ordinary graph solver. Its generated program allocates five stacks: front for the current distance layer, back for the next layer, edges as a temporary buffer, goal, and distance.
- Fetch the outgoing edges of a popped front vertex. A zero edge pushes its destination to front; a unit edge pushes its destination to back. When front empties, increase distance and transfer back to front. Repeated copies of a vertex cause no repeated expansion because getEdges returns edges only on its first call for that vertex.
- Always test whether the popped vertex is the goal before fetching its edges. This also handles Start=End. In the first official graph, the zero edges 0→3→1 are processed in layer zero, then 1→2 is processed in layer one. The second official graph has no path from 1 to 0, so the program returns −1.
- This solves the full graph domain in linear instructions, but the five allocated stacks limit its scoring percentage to 40% per solved subtask under the original table. It does not claim the two-stack full-score optimization. The generated code is comfortably below the ten-million instruction validity limit.
Why it works
At layer d, front contains candidates reached at cost d and back candidates at cost d+1. Zero-edge expansion stays in the current layer, and only after it is exhausted does the program advance to the next layer. Thus a vertex’s first expansion occurs at its shortest distance. The one-shot getEdges behavior suppresses later expansions without losing an edge needed at a smaller distance. The first goal occurrence returns its minimum distance. Both work stacks empty exactly when all reachable vertices have been expanded.
Watch out. getEdges pushes a weight followed by its destination at the top; pop both correctly. Fetching an already expanded vertex is a no-op. Respect the actual Stacklang submission format and distinguish full graph correctness from maximum scoring.
Commented C++17 solution
Compile and run this generator without input; save stdout as stacklang.txt. Append that file to a graph input for the official local interpreter, or submit the Stacklang file through the contest interface. Five stacks solve all graph cases but receive the table’s 40% stack factor, not maximum score.
#include<iostream>
using namespace std;
int main(){
// Offline generator: submit its output as stacklang.txt.
cout<<R"(alloc 5 front back edges goal distance
getStart front
getEnd goal
push distance 0
label nextVertex
if empty front goto nextLayer
if equal front goal goto found
getEdges edges front
pop front
label nextEdge
if empty edges goto nextVertex
if equal edges 0 goto zeroEdge
pop edges
push back edges
pop edges
goto nextEdge
label zeroEdge
pop edges
push front edges
pop edges
goto nextEdge
label nextLayer
if empty back goto unreachable
add distance 1
label transfer
if empty back goto nextVertex
push front back
pop back
goto transfer
label found
return distance
label unreachable
return -1
)";
}