a540. CPE：Geonosis (UVa 13211)

題目描述

Geonosis 的通訊網有 n 座塔。wij 是從塔 i 直接傳訊到塔 j 的耗能，方向不同時耗能可以不同。拆毀一座塔之前，需要的能量是當時所有仍存在、彼此不同的有序塔對 (u,v) 之最短傳訊耗能 d(u,v) 的總和；路徑只能經過當時仍存在的塔。拆毀後該塔不再參與計算。依給定順序拆毀全部塔，求總耗能。

輸入格式

第一行為測試筆數 t。每筆先給 n（1 ≤ n ≤ 500），接著 n 行各 n 個整數 wij。對角線 wii=0，其餘 1 ≤ wij ≤ 10000。最後一行為 0 至 n−1 的排列，表示拆毀順序。

輸出格式

每筆輸出一行拆毀整座要塞的總能量。

來源：UVa 13211 — Geonosis。本敘述依原題規格重新撰寫。