d095: P_7_1 探索距離
Tags : ch7
Accepted rate : 4人/5人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-12-27 20:15

Content

 輸入一個有向圖 $G$ 與一個起點 $s$ ,請計算由 $s$ 出發可以到達的點數(不包含 $s$),並且計算這些可以到達的點與 $s$ 的距離和,假設每個邊的長度均為 $1$ 。兩點之間可能有多個邊,邊的起點與終點未必不同。

Input

 第一行是兩個正整數 $n$ 與 $m$ ,代表圖的點數與邊數,圖的點是以 $0 \sim (n-1)$ 編號,第二行是 $s$ 的編號,接下來有 $m$ 行,每一行兩個整數 $a$ 與 $b$ 代表一個邊 $(a,b)$ 。$n$ 不超過 $100$,$m$不超過 $4000$。

Output

 第一行輸出可以到達的點數,第二行輸出與 $s$的距離總和。

Sample Input #1
7 6
1
5 1
1 3
1 4
2 3
4 6
6 0
Sample Output #1
4
7
Sample Input #2
3 2
0
1 2
2 1
Sample Output #2
0
0
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
ch7
出處:
Prof. Wu [管理者:
ktlai (K.我已霸榜.Tlai)
]


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