P3451 [POI 2007] ATR-Tourist Attractions

[English Edition](/paste/gu4ksinh)

You are given an undirected graph with $n$ vertices and $m$ edges, where each edge has a weight. You need to find a shortest path from $1$ to $n$ that, while satisfying the given $g$ constraints, can stop at every vertex numbered from $2$ to $k+1$. Each constraint is of the form $r_i, s_i$, meaning that you must have stopped at $r_i$ before stopping at $s_i$. Note that “stop” here does not mean merely passing through.

The first line contains three integers $n, m, k$. Each of the next $m$ lines contains three integers $p_i, q_i, l_i$, meaning there is an edge of weight $l_i$ between $p_i$ and $q_i$. The next line contains an integer $g$. Each of the next $g$ lines contains two integers $r_i, s_i$, representing one constraint.

Output a single integer on one line — the length of the shortest path.

Constraints: - For $100\%$ of the testdata, the following hold: - $2 \le n \le 2 \times 10^4$. - $1 \le m \le 2 \times 10^5$. - $0 \le k \le \min(20, n-2)$. - $1 \le p_i < q_i \le n$. - $1 \le l_i \le 10^3$. - $r_i, s_i \in [2, k+1],\ r_i \ne s_i$. - There are no multiple edges, and a solution always exists. Translated by ChatGPT 5