科學家發現了 $n$ 種病毒,編號分別是 $1$ 到 $n$,已知每一種病毒可以用一個RNA 序列來表達,RNA序列是一個長度為 $m$ 的字串,其中包含 A、U、C、G、@ 等字元,其中 @ 為科學家沒觀察清楚的位置,可能為 A、U、C、G 其中任何一種。
科學家也研究出了這些病毒的演化關係,除了一個最原始的病毒以外,每一種病毒都是從另一個病毒演化而來的,這些病毒會構成一個樹狀結構的病毒族譜(如圖)。
兩個 RNA 序列的的距離定義為它們的漢明距離,也就是相異的位數個數。更具體的說,對於兩個長度都是$m$ 的 RNA 序列$a, b$,它們的漢明距離就是有幾個位置 $i$ 滿足 $a_i \neq b_i$。
你想知道目前的病毒族譜的每一個 RNA 序列中的 @ 字元的填入 A、U、C、G 中的其中一個字元後,每一個病毒與它演化來源的病毒的距離總合最小值是多少?
第一行包含兩個正整數 $n, m (1\leq n \leq 1000, 1\leq m \leq 80)$。
接下來 $n$ 行,每行表示一種病毒,包含兩個整數 $i, j$ 與一個字串 $s$,表示編號 $i$ 的病毒是從編號 $j$ 的病毒演化而來的,且編號 $i$ 的病毒的 RNA 序列為 $s$。若編號 $i$ 的病毒是最原始的病毒,則 $j=i$,保證這樣的病毒只會有一個。
配分
輸出每種病毒到它演化來源的病毒的距離總和最小值。
2 3 1 1 AAC 2 1 A@@
0
6 1 1 1 @ 2 1 @ 3 1 C 4 1 C 5 2 A 6 2 A
1
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
37843 | edoctopus322 ... (Moon Jam) | f582 | 697 | 2023-10-13 21:27 |