蓝桥公园 ### 题目描述 小明喜欢观景，于是今天他来到了蓝桥公园。 已知公园有 $N$ 个景点，景点和景点之间一共有 $M$ 条道路。小明有 $Q$ 个观景计划，每个计划包含一个起点 $st$ 和一个终点 $ed$，表示他想从 $st$ 去到 $ed$。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？ ### 输入描述 输入第一行包含三个正整数 $N,M,Q$ 第 $2$ 到 $M + 1$ 行每行包含三个正整数 $u,v,w$，表示 $u\leftrightarrow v$ 之间存在一条距离为 $w$ 的路。 第 $M+2$ 到 $M + Q-1$ 行每行包含两个正整数 $st,ed$，其含义如题所述。 $1\leq N\leq 400$，$1\leq M \leq \dfrac{N\times(N - 1)}{2}$，$Q\leq 10^3$，$1\leq u,v,st,ed \leq n$，$1\leq w \leq 10^9$ ### 输出描述 输出共 $Q$ 行，对应输入数据中的查询。 若无法从 $st$ 到达 $ed$ 则输出 $-1$。 ### 输入输出样例 #### 示例 1 >输入 ```txt 3 3 3 1 2 1 1 3 5 2 3 2 1 2 1 3 2 3 ``` >输出 ```txt 1 3 2 ```