A2448. ATR-Tourist Attractions
编程题
省选/NOI-
知识点
题目描述
[English Edition](/paste/gu4ksinh)给出一张有 $n$ 个点 $m$ 条边的无向图，每条边有边权。
你需要找一条从 $1$ 到 $n$ 的最短路径，并且这条路径在满足给出的 $g$ 个限制的情况下可以在所有编号从 $2$ 到 $k+1$ 的点上停留过。
每个限制条件形如 $r_i, s_i$，表示停留在 $s_i$ 之前必须先在 $r_i$ 停留过。
**注意，这里的停留不是指经过**。
你需要找一条从 $1$ 到 $n$ 的最短路径，并且这条路径在满足给出的 $g$ 个限制的情况下可以在所有编号从 $2$ 到 $k+1$ 的点上停留过。
每个限制条件形如 $r_i, s_i$，表示停留在 $s_i$ 之前必须先在 $r_i$ 停留过。
**注意，这里的停留不是指经过**。
输入格式
第一行三个整数 $n,m,k$。
之后 $m$ 行，每行三个整数 $p_i, q_i, l_i$，表示在 $p_i$ 和 $q_i$ 之间有一条权为 $l_i$ 的边。
之后一行一个整数 $g$。
之后 $g$ 行，每行两个整数 $r_i, s_i$，表示一个限制条件。
之后 $m$ 行，每行三个整数 $p_i, q_i, l_i$，表示在 $p_i$ 和 $q_i$ 之间有一条权为 $l_i$ 的边。
之后一行一个整数 $g$。
之后 $g$ 行，每行两个整数 $r_i, s_i$，表示一个限制条件。
输出格式
输出一行一个整数，表示最短路径的长度。
输入输出样例
输入 #1
8 15 4 1 2 3 1 3 4 1 4 4 1 6 2 1 7 3 2 3 6 2 4 2 2 5 2 3 4 3 3 6 3 3 8 6 4 5 2 4 8 6 5 7 4 5 8 6 3 2 3 3 4 3 5
输出 #1
19
说明/提示
对于 $100\%$ 的数据， 满足：
- $2\le n\le2\times10^4$
- $1\le m\le2\times10^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\not=s_i$
- 保证不存在重边且一定有解。
- $2\le n\le2\times10^4$
- $1\le m\le2\times10^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\not=s_i$
- 保证不存在重边且一定有解。