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 | |