Submit Ranklist
Problem : 343 - pC.老鼠愛大米
Problem Statistics
Solved Member:
21 Submission:
82 User Tried:
27 Statement:
附中的老鼠們平常生活在一個複雜的地道系統中! 這個系統中有N個老鼠窩跟M條單向的地道(為了避免卡住，老鼠們的世界也是有秩序的)，每個老鼠窩都住著很多隻老鼠，我們將鼠窩編號為1~N，每條單向地道連接兩個老鼠窩。兩個老鼠窩之間可能不只有一條地道，也可能地道的起點和終點是同一個老鼠窩。
其中編號K的老鼠窩有很多很多的大米，大米的擁有者——老鼠威廷，死前說了這麼一段話：「想要我的大米嗎？如果想要的話那就到我的老鼠窩吧，我全都放在那裡了！」，於是附中的老鼠們爭相前往探險，便開啟了大地道時代。
由於老鼠們不確定自己的鼠窩有沒有辦法到達編號K的鼠窩，他們請你幫忙寫程式計算共有幾隻老鼠有辦法找到大米。
Input:Output:
第1行有三個正整數N, M, K，表示有N個老鼠窩，M條單向地道，以及大米位在編號K的老鼠窩。
第2~M+1行，每行有兩個正整數a, b，表示有一條單向地道從a連向b。
第M+2行有N個非負整數，依序代表編號1~N的老鼠窩有多少老鼠。
一個正整數表示有多少老鼠可以走到編號為K的老鼠窩。
Sample Input:Sample Output:
5 5 3
1 2
2 1
3 1
4 3
2 3
7 8 6 2 7
23
HINT:
占總分30%的資料，滿足: N<=500 M<=1,000
占總分60%的資料，滿足: N<=1,000 M<=4,000
全部的資料滿足以下條件:
1<= N <=100,000
1<= M<=500,000
1<= K <= N
0<= 一個鼠窩內的老鼠數量 <= 100
Source:
103附中校內賽
Problem Setter
bigelephant29 Testdata:
| Test | Time | Memory | Score |
|---|
| 0 | 1000ms | 262144kb | |
| 1-1 | 1000ms | 262144kb | 30 |
| 1-2 | 1000ms | 262144kb | |
| 2-1 | 1000ms | 262144kb | 30 |
| 2-2 | 1000ms | 262144kb | |
| 3-1 | 1000ms | 262144kb | 40 |
| 3-2 | 1000ms | 262144kb | |
| 3-3 | 1000ms | 262144kb | |