f413.
Shortest Path Without x
內容
給一個圖包含 $n$ 個點及 $m$ 條有權重的有向邊，另外有 $Q$ 次查詢，每次查詢 $(x, u, v)$ 要輸出從 $u$ 走到 $v$ 不經過 $x$ 的最短路徑長度。
輸入說明
輸入第一行依序包含三個整數 $n, m, Q$，分別表示圖上的節點數，圖上的邊數，查詢的數量。
接下來的 $m$ 行，每行有三個整數 $u, v, w$ 表示有一條從 $u$ 到 $v$ 的有向邊，長度是 $w$。
接下來的 $Q$ 行，每行有三個整數 $x, u, v$ 表示要查詢 $u$ 走到 $v$ 不經過 $x$ 的最短路徑長度。
輸入範圍限制
- $3 \leq n \leq 100$
- $0 \leq m \leq 10000$
- $0 \leq Q \leq 100000$
- 對於每一條邊都滿足 $0\leq u, v \leq n-1$, $0 \leq w \leq 100$
- 對於每一個查詢都滿足$0\leq x, u, v \leq n-1$, $u \neq x, v \neq x$
輸出說明
依照每一個查詢的順序，輸出最短路徑長度，若無法到達則輸出 $-1$。
範例輸入
#1
4 4 3 0 1 1 1 2 1 2 3 2 0 3 5 1 0 3 3 0 2 1 0 2
範例輸出
#1
5 2 -1
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (5%): 0.5s , <1M
公開 測資點#1 (5%): 0.5s , <1M
公開 測資點#2 (5%): 0.5s , <1M
公開 測資點#3 (5%): 0.5s , <1M
公開 測資點#4 (5%): 0.5s , <1M
公開 測資點#5 (5%): 0.5s , <1M
公開 測資點#6 (5%): 0.5s , <1M
公開 測資點#7 (5%): 0.5s , <1M
公開 測資點#8 (5%): 0.5s , <1M
公開 測資點#9 (5%): 0.5s , <1M
公開 測資點#10 (5%): 0.5s , <1M
公開 測資點#11 (5%): 0.5s , <1M
公開 測資點#12 (5%): 0.5s , <1M
公開 測資點#13 (5%): 0.5s , <1M
公開 測資點#14 (5%): 0.5s , <1K
公開 測資點#15 (5%): 0.5s , <1K
公開 測資點#16 (5%): 0.5s , <1K
公開 測資點#17 (5%): 0.5s , <1K
公開 測資點#18 (5%): 0.5s , <1K
公開 測資點#19 (5%): 0.5s , <1K
公開 測資點#0 (5%): 0.5s , <1M
公開 測資點#1 (5%): 0.5s , <1M
公開 測資點#2 (5%): 0.5s , <1M
公開 測資點#3 (5%): 0.5s , <1M
公開 測資點#4 (5%): 0.5s , <1M
公開 測資點#5 (5%): 0.5s , <1M
公開 測資點#6 (5%): 0.5s , <1M
公開 測資點#7 (5%): 0.5s , <1M
公開 測資點#8 (5%): 0.5s , <1M
公開 測資點#9 (5%): 0.5s , <1M
公開 測資點#10 (5%): 0.5s , <1M
公開 測資點#11 (5%): 0.5s , <1M
公開 測資點#12 (5%): 0.5s , <1M
公開 測資點#13 (5%): 0.5s , <1M
公開 測資點#14 (5%): 0.5s , <1K
公開 測資點#15 (5%): 0.5s , <1K
公開 測資點#16 (5%): 0.5s , <1K
公開 測資點#17 (5%): 0.5s , <1K
公開 測資點#18 (5%): 0.5s , <1K
公開 測資點#19 (5%): 0.5s , <1K
提示 ：
$O(n^3 \log n)$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||