a516. [模板] Floyd-Warshall / XX老師的AA語課

內容

在XX老師的AA語課上，因為太無聊了，大家都不想專心上課，有些人開始想和其他人聊天，但被XX老師發現會掀起一場腥風血雨，他們決定私底下偷偷傳紙條。

只有坐在附近的學生可以傳遞紙條，坐在附近的學生之間也有不固定的距離 (總是會有人喜歡亂跑)。

為了降低被XX老師發現的風險，傳紙條的距離越短越好，現在有Q個學生想要傳紙條，請問各個紙條傳遞的最短距離是多少?

輸入說明

一開始有三正整數 $N,M,Q(N\le 300,M\le (\frac{n(n-1)}{2}),Q\le 2\times 10^5)$ ，代表有N個學生，M個坐在附近的關係，Q個學生想要傳紙條，接下來有M行，每行有三個正整數 $u,v,w(1\le u,v \le N,w\le 5\times 10^4)$ 代表u和v可以互相傳紙條且他們之間的距離是w，最後Q行，每行有兩個正整數 $x,y(x,y\le N)$ ，代表x學生想傳紙條給y學生。

*可能會有重邊

*自己傳紙條給自己距離為 0 (就是會有人這麼閒)

輸出說明

對於每次傳紙條，輸出紙條傳遞的最短距離。

如果沒辦法將紙條傳到y則輸出-1

範例輸入 #1

範例輸出 #1

4
1
1

測資資訊：

記憶體限制： 128 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

提示：

多點多源最短路

範測1:

學生 1 可以直接傳紙條給 3 ，距離為 4，也可以傳給 2 再傳給 3，距離為 3 + 1也是 4

學生 1 可以直接傳紙條給 2 ，距離為 1

學生 2 可以直接傳紙條給 1 ，距離為 1

標籤:

Floyd-Warshall 最短路

出處:

[管理者：

211096@stu.c... (唐狗針)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」