蓝桥杯vip试题（蓝桥公园）坑题

2023-03-28 11:14 作者:繁花5138 0人读过 | 我要投稿

题目描述

小明喜欢观景，于是今天他来到了蓝桥公园。

已知公园有 $N$ 个景点，景点和景点之间一共有 $M$ 条道路。小明有 $Q$ 个观景计划，每个计划包含一个起点 $s t$ 和一个终点 $e d$ ，表示他想从 $s t$ 去到 $e d$ 。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？

输入第一行包含三个正整数 $N, M, Q$

第 $2$ 到 $M + 1$ 行每行包含三个正整数 $u, v, w$ ，表示 $u \leftrightarrow v$ 之间存在一条距离为 $w$ 的路。

第 $M + 2$ 到 $M + Q - 1$ 行每行包含两个正整数 $s t, e d$ ，其含义如题所述。

$1 \leq N \leq 400$ ， $1 \leq M \leq N \times ( N - 1 )/2$ ， $Q \leq 1 0^^{3}$ ， $1 \leq u, v, s t, e d \leq n$ ， $1 \leq w \leq 1 0^^{9}$

输出共 $Q$ 行，对应输入数据中的查询。

若无法从 $s t$ 到达 $e d$ 则输出 $-1$ 。

代码分析: