內容
-------不想廢話了--------
給定一個有N個點的單向無權圖(編號1~N)，請問從點i走k步後到點j共有多少種走法呢?
給定一個有N個點的單向無權圖(編號1~N)，請問從點i走k步後到點j共有多少種走法呢?
輸入說明
每組測資的第一行給定節點數N及步數k
接下來好多行敘述此單向圖，
每一行的x y s代表從點x直達點y共有s條路徑，而每條路徑都是一步到達
以0 0 0代表此圖敘述結束
例如第一組範例測資:
3 3
1 2 2
2 1 1
2 3 4
2 2 1
3 1 2
0 0 0
代表從點1到點2共有2條路徑直達
注意2 2 1代表點2到點2有1條路徑，是合法輸入
若有未敘述到的代表那兩點間直達路徑數是0
測資保證不會有重覆輸入或不合法的節點編號出現
然後輸入詢問數Q，代表有Q行詢問
接下來Q行各有兩個數i j，請對每一組i j 輸出從i出發，走k步剛好到達j共有多少種走法
另外因為答案可能好大，所以請輸出 mod 5281的答案
注意途中可以先經過j沒關係，只要第k步能剛好到達j就行了
走過的路徑都可以再走。
範圍: 1<=N<=50，Q<=N2，0<=s<=20，1<=k<=10000000
接下來好多行敘述此單向圖，
每一行的x y s代表從點x直達點y共有s條路徑，而每條路徑都是一步到達
以0 0 0代表此圖敘述結束
例如第一組範例測資:
3 3
1 2 2
2 1 1
2 3 4
2 2 1
3 1 2
0 0 0
代表從點1到點2共有2條路徑直達
注意2 2 1代表點2到點2有1條路徑，是合法輸入
若有未敘述到的代表那兩點間直達路徑數是0
測資保證不會有重覆輸入或不合法的節點編號出現
然後輸入詢問數Q，代表有Q行詢問
接下來Q行各有兩個數i j，請對每一組i j 輸出從i出發，走k步剛好到達j共有多少種走法
另外因為答案可能好大，所以請輸出 mod 5281的答案
注意途中可以先經過j沒關係，只要第k步能剛好到達j就行了
走過的路徑都可以再走。
範圍: 1<=N<=50，Q<=N2，0<=s<=20，1<=k<=10000000
輸出說明
對每一個詢問i j
輸出從i出發，走k步剛好到達j共有多少種走法 mod 5281的答案
輸出從i出發，走k步剛好到達j共有多少種走法 mod 5281的答案
範例輸入
#1
3 3 1 2 2 2 1 1 2 3 4 2 2 1 3 1 2 0 0 0 9 1 2 1 1 2 1 1 3 2 2 2 3 3 1 3 2 3 3 2 4 1 1 1 1 2 3 2 1 5 0 0 0 3 1 1 1 2 2 1
範例輸出
#1
6 18 11 8 21 12 4 4 16 271 93 155
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (100%): 3.0s , <1M
公開 測資點#0 (100%): 3.0s , <1M
提示 ：
O(N3logk)
標籤:
出處:
國文課時的靈機一動(誤
[管理者：
david942j
(文旋)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 25538 |
|
d769 | 353 | 2021-05-30 21:39 |