← 返回题目
题库练习 ATR-Tourist Attractions
← 上一题 下一题 →

A2448 | ATR-Tourist Attractions

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

[English Edition](/paste/gu4ksinh)给出一张有 $n$ 个点 $m$ 条边的无向图，每条边有边权。

你需要找一条从 $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$，表示一个限制条件。

输出格式

输出一行一个整数，表示最短路径的长度。

输入输出样例

输入 #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
C++ 编辑器
输入
输出