e792. a3.旅行(Trip)
Tags : floyd 任2點最短距
Accepted rate : 214人/243人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-12-29 16:55

Content

Y19m12_a03.旅行(Trip)TOI練習賽2019/12

問題敘述  {題目連結}

小軒最近考上研究所,想出去旅行。小軒所在的星球,有許多國家,國家之間只能用飛機來通行。然而,飛機只有特定的航班,並不是所有國家都可以互通的。小軒這時候要來安排他的旅途,他必須知道是否可以從某個國家出發經由搭飛機,去到另一個國家。請你寫一個程式來幫助小軒。

 評分說明
此題目測資分成兩組。各組詳細限制如下。
第一組 (30 分) : 2≤N ≤5、1≤M≤ 20、1≤Q≤10。
第二組 (70 分) : 無限制。

Input

第一列有三個正整數N、M、Q(2≤N≤200、1≤M≤N(N-1)、1≤Q≤20000),代表有N個國家(國家的編號為0~N-1),M個航班,以及Q次查詢。

接著M列為航班資訊,每列有兩個正整數,為飛機的出發地與目的地。再接著的Q列為小軒的查詢,每列有兩個正整數A、B,代表小軒想要查詢A國是否可以經由坐飛機到B國。

Output

對每筆查詢資料,如果A國可以經由坐飛機到B國,請輸出YES;反之,請輸出NO。

Sample Input #1
3 2 2
0 1
1 2
0 2
1 0
Sample Output #1
YES
NO
Sample Input #2
5 4 5
4 3
0 3
3 1
1 2
4 3
3 2
3 0
1 0
3 4
Sample Output #2
YES
YES
NO
NO
NO
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :

非官方測資,自己黑白舞的,若有誤請見諒並不吝告知!

Tags:
floyd 任2點最短距
出處:
2019年12月TOI練習賽 [管理者: p3a_owhj (阿普二信) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
41513 lbm00138 (bits/stdc++.h) e792
用 BFS
88 2024-08-02 23:58
23086 joeliao (RRRrrrr!!!) e792
真的想不到的話
1092 2020-10-21 18:58