题目描述
译自 POI 2007 Stage 1.「Tourist Attractions」
给定 n 个顶点和 m 条边组成的一张图,边有长度,且要求按照一定的顺序停留 2…k+1 共 k 个点(可以经过这些点但不停留),求最短的符合要求的从 1 出发到 n 的路径。保证存在这样的路径。
输入格式
第一行有三个数 n,m 和 k,且保证 k≤n−2.
接下来 m 行每行三个整数 pi,qi,li(1≤pi<qi≤n,1≤li≤1 000),表示一条连接 pi 和 qi 的长度为 li 的边。
接下来一行一个整数 g(0≤g≤2k(k+1)),表示有 g 条对这 k 个点访问顺序的限制条件。
接下来 g 行每行有两个整数 ri 和 si,表示一条要求,先在 ri 停留,后在 si 停留。
输出格式
输出满足要求的路径的最短长度。
数据范围与提示
2≤n≤20 000,1≤m≤200 000,0≤k≤min(n−2,20)