下圖表示有 11 個路口(以 '*' 表示) 和 10 條道路。
最近有幾個地方產生交通壅塞,專家建議將雙向道改成單向道,然而這項工程要特別小心,否則將會有些地方被孤立無法到達,又或者使兩地的最短路徑增大。
經過數次討論,市長的顧問打算同意兩地之間的最短距離增大 A 倍加一個常數 B,也就是說當兩地最短距離 x,更改過後的距離最多為 Ax+B。
Input
輸入有多組測資,每組測資有兩張圖的描述。
每組第一行有一個整數 n (3 <= n <= 100),表示路口的個數,路口編號為 1, 2, 3, ..., n。
接下來會有 n 行,在第 i 行(1 <= i <= n) 上會有數個整數,表示路口 i 相連到其他路口的資訊。
接下來會有 n 行,在第 i 行(1 <= i <= n) 上會有數個整數,表示在新的規劃中,路口 i 相連到其他路口的資訊。
最後一行會有兩個整數 A, B (0 <= A, B <= 10)
Output
對於每組測資,輸出 "Yes" 或 "No" 表示是否接受新的建議。
Sample Input
5
1 2 3
2 1 5
3 4 5 1
4 3 5
5 2 3 4
1 2
2 5
3 1 4
4 5
5 3
1 2
5
1 2 3
2 1 5
3 4 5 1
4 3 5
5 2 3 4
1 2
2 5
3 1 4
4 5
5 3
2 0
3
1 2
2 1 3
3 1 2
1 2
2 3
3 1
0 2
0
Sample Output
Yes
No
Yes
沒有留言:
張貼留言