f413: Shortest Path Without x
Tags : 分治法 最短路徑
Accepted rate : 9人/10人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-11-11 18:20

Content

給一個圖包含 $n$ 個點及 $m$ 條有權重的有向邊,另外有 $Q$ 次查詢,每次查詢 $(x, u, v)$ 要輸出從 $u$ 走到 $v$ 不經過 $x$ 的最短路徑長度。

Input

輸入第一行依序包含三個整數 $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$
Output

依照每一個查詢的順序,輸出最短路徑長度,若無法到達則輸出 $-1$。

Sample Input #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
Sample Output #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
Hint :

$O(n^3 \log n)$

Tags:
分治法 最短路徑
出處:
海牛自編題 [管理者:
cthbst (吳宗達)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」