585 . DNA序列密碼問題
Description
一些生物的複雜結構可以用其DNA序列來表示。而DNA序列又可以表示為帶有標記的核苷酸字串。最近，佳佳大學生物資訊學研究小組的一項工作表明，大多數蛋白質序列可以從核苷酸資料庫記錄中推導出來。研究小組的科學家們用密碼學方法將DNA序列變換為2維Cray碼後發現，任一DNA的Cray碼序列S具有如下性質：
1. 序列S: (x1,y1), (x2,y2), ..., (xn,yn)是一個有限序列;
2. 序列S中各項 (xi,yi) 均落在一個網格邊長為 1 的 300乘以3000平面網格 N 的網格點上
3. 序列S中各項最多分布在網格 N 的 3 行中。
科學家們發現，若將序列S的每一項都看作平面上一個點，從序列的任意一點出發，連接序列中每個點恰好一次，又回到出發點的最短平面迴路T的長度與該序列表示的DNA密碼密切相關。為了有效地破譯DNA密碼，科學家們希望設計出一個高效能的計算程式，能對給定DNA的Cray碼序列S，快速計算出其最短迴路T的長度。
Input Format
輸入檔案中可能包含多筆測試資料:
第一列有三個整數為 na, nb, nc, 分別代表網格上某三行的點數。(0<=na, nb, nc<=1300)
第二列有三個整數為 ya, yb, yc, 分別代表這三行的位置。(0<=ya< yb< yc<=300)
接下來的na列每一列包含一個整數，依序為 a1, a2, ..., a_(na)
再下來的nb列每一列包含一個整數，依序為 b1, b2, ..., b_(nb)
最後的nc列每一列包含一個整數，依序為 c1, c2, ..., c_(nc)
序列a, b, c分別是遞增的，而且均介於0以及3000之間。
Output Format
對每一筆測試資料，輸出所找到的序列S的最短迴路T的長度值，精確到小數點後2位。
Sample Input 1
2 1 2 1 2 3 5 7 6 5 7 2 1 2 1 2 3 5 7 6 5 7
Sample Output 1
8.83 8.83
Hints
Problem Source
Migrated from old NTUJ.
NOI2002福建省, DarkTmt
Subtasks
| No. | Testdata Range | Score |
|---|