TopCoder

User's AC Ratio

98.1% (53/54)

Submission's AC Ratio

65.2% (86/132)

Description

轉圈圈捷運公司一向是以多樣性的路線,繞不完的圈圈,以及每條路線上搭配的行程而享譽國際。不過也因為這樣,太多的路線交錯複雜,時再也沒有人能夠分清楚哪一段是哪的路線,以及總共有多少的圈圈。

轉圈圈捷運公司的董事長漢米頓,一直有想要作一件事情,就是想要把捷運路線上,每一種圈圈的路線要坐上一遍,而他的這個計畫已經開始實施了。

但是,幾天之後他發現了他的想法幾乎不可能實現:他已經轉到快要吐出來的!而且當他嘗試著要把所有的環狀路線全部都列出來,寫在他的記事本上的時候,他才發現這是一個很難的問題,他根本不知道有多少條的圈圈路線!他列出了很多,也坐過了很多圈圈的路線,可是他沒有辦法知道說又沒有漏了哪一條環狀路線沒有坐過。

漢米頓花了很多的時間,才發現了這個問題很難,很難。不過漢米頓並不放棄,雖然他以他一個人的力量沒有辦法做到,但是他想到了一個辦法!

轉圈圈捷運公司在近日內,會舉辦一個轉圈圈換獎品的活動,如果搭乘捷運的旅客所搭乘的路線,起點和終點是同一個的話,就可以得到一份價值150元的獎品。當然,這條路線至少要有搭上捷運才算,直接進站又出站的話可是不能算的!

轉圈圈捷運公司在計算車資的時候,是依照旅客從進站到出站的時間來計算的,如果坐了15分鐘的車,那麼車費就會是15元。

漢米頓對於自己的想到的這個辦法很滿意,但是他還是有一點擔心:如果有人坐環狀路線的車資比150元還要少,那公司可就虧大了…所以現在的他正在想辦法找找看有沒有哪一條環狀路線上的車資是會小於150元的。

看到漢米頓這麼煩惱,聰明的你應該想到好方法幫幫他了吧!可以寫個程式幫忙他找到在轉圈圈捷運公司的路線中,所花費時間最少的一條環狀路線,要坐多久呢?

Input Format

輸入檔中有許多組輸入,每組輸入的第一行有一個數字 N(1 ≦ N ≦ 100),代表總共有 N 個捷運站。接下來有 N 行,每行有 N 個數字、以空白分隔,第 i 行的第 j 個數字 Tij 代表編號 i 的捷運站有一條路線到編號 j 的捷運站,車程 Tij 分鐘(0 <= Tij <= 1000),如果這個數字是 0 代表兩站之間沒有直接相連。N = 0 表示檔案結束。

Output Format

對每組輸入輸出一行,包含一個數字,表示花費最短的環狀路線所花的時間。如果找不到任何一條環狀路線,則輸出 -1。

Sample Input

2
0 20
0 0
2
0 1
1 0
4
0 0 2 0
4 0 0 0
0 3 0 1
0 1 0 0
0

Sample Output

-1
2
8

Hints

Problem Source

原TIOJ1096 / NPSC2006初賽(prob E)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536