散文網(wǎng) » 科技 »學習 » 藍橋杯vip試題（藍橋公園）坑題

藍橋杯vip試題（藍橋公園）坑題

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

題目描述

小明喜歡觀景，于是今天他來到了藍橋公園。

已知公園有? $N$ ?個景點，景點和景點之間一共有? $M$ ?條道路。小明有? $Q$ ?個觀景計劃，每個計劃包含一個起點? $s t$ ?和一個終點? $e d$ ，表示他想從? $s t$ ?去到? $e d$ 。但是小明的體力有限，對于每個計劃他想走最少的路完成，你可以幫幫他嗎？

輸入第一行包含三個正整數(shù)? $N, M, Q$

第? $2$ ?到? $M + 1$ ?行每行包含三個正整數(shù)? $u, v, w$ ，表示? $u ? v$ ?之間存在一條距離為? $w$ ?的路。

第? $M + 2$ ?到? $M + Q ? 1$ ?行每行包含兩個正整數(shù)? $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$ ?行，對應(yīng)輸入數(shù)據(jù)中的查詢。

若無法從? $s t$ ?到達? $e d$ ?則輸出? $?1$ 。

代碼分析: