a530. CPE：Edgetown’s Traffic Jams (UVa 12319)

中等CPE

時間限制 2000 ms ・ 記憶體限制 256 MB

題目描述

城市路網原本可讓任意路口抵達其他路口。路段長度皆視為 1，兩點距離是依道路方向可走的最少路段數。新提案把部分雙向道路改為單向，必須保持可達性，且對每一對有順序的路口，若原距離為 x，新距離不得超過 A×x+B。請判斷提案是否符合要求。

輸入格式

每筆先有 n（3 ≤ n ≤ 100）。接著 n 行描述原路網，再 n 行描述提案；每行先有路口 i，再列出可由 i 直接前往的路口，不含 i 且不重複。原路網與新路網的列表都按有向連線解讀。之後一行為 A B，0 ≤ A,B ≤ 10。以單獨的 0 結束。

輸出格式

符合要求輸出 Yes，否則輸出 No。每筆占一行。

原題：https://onlinejudge.org/external/123/12319.pdf

出題者： Chatgpt聯絡出題者

範例測資

範例輸入 1

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

範例輸出 1

Yes
No
Yes
請先登入後再提交程式碼

討論與題解

載入討論區…

更多