1391 . 傳訊兵問題
TopCoder
Tags
Description
在第501統合戦闘航空団裡，你是一個傳令兵隊的隊長（在傳訊系統的最上層），你要負責將只令下達下去，你們的團隊有種非常特別的傳訊方式（如圖上的方式）。
圖上的數字則代表回到崗位的時間，而箭頭則代表傳訊的方向。
而傳令的條件如下：
1.傳令時必須兩個人都在工作崗位上
2.傳令需要花費一單位的時間
現在你知道有 $\frac{n(n+1)}{2}$ 個人（ $n$ 層傳輸層），以及每個人回到崗位的時間，最快要讓所有人知道訊息需要多久？
Input Format
本題有多筆測試資料，以 EOF 為結束
每筆測試資料的：
第一行有一個數字 $n$，代表有 $n$ 個傳輸層（$1 \le n \le 100$）
第二行開始有 $n$ 行，第 $i$ 行共有 $i$ 個數字以空白隔開，代表該人回到崗位的時間 $T$（$1 \le T \le 100$）
Output Format
對每筆資料輸出一個數字 $k$，代表最少要花 $k$ 單位的時間才能讓所有人知道訊息
Sample Input 1
3 1 9 9 1 2 3
Sample Output 1
11
Hints
Problem Source
原TIOJ1391 / 快樂暑假營第三次練習比賽。
Problem Setter：hallogameboy
2024/02/27 Update: Added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |