P1811 Shortest Path

Given an undirected graph with $N$ vertices and $M$ edges, where each edge has weight $1$. You are also given $K$ ordered triples $(A,B,C)$, meaning that after moving from $A$ to $B$, you are not allowed to move to $C$. Note that the triples are ordered; for example, it is allowed to go from $B$ to $A$ and then to $C$. Under the constraints given by the $K$ triples, find the shortest path from node $1$ to node $N$, and output any valid path. A Check will verify your output.

The first line contains three integers $N$, $M$, $K$, as described above. Each of the next $M$ lines contains two integers $A$, $B$, indicating there is an edge between $A$ and $B$. Each of the next $K$ lines contains three integers $(A,B,C)$ describing one triple.

Output consists of two lines. The first line contains a single integer $S$, the length of the shortest path. The second line contains $S+1$ integers, the sequence of nodes visited from $1$ to $N$.

For 40% of the testdata, $N \le 10$, $M \le 20$, $K \le 5$. For 100% of the testdata, $N \le 3000$, $M \le 20000$, $K \le 100000$. Translated by ChatGPT 5