TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

80.0% (8/10)

Submission's AC Ratio

22.6% (28/124)

Description

Tourist旅行社預告了一系列的新行程。為了慶祝他們的開幕10週年,這些新行程的價格都是令人無法想像地便宜,且可以在任意時間出發。
所有的新行程包含了$N$個不同的景點,每一個行程的起點和終點是不同的景點,中途不會經過別的景點。行程們都有不同的價格。為了方便,將景點編號為1到N。

卡爾是一個旅行家,自然不能放過本次的行程大特價,可惜的是,卡爾所居住的地點並不在這$N$個景點當中。幸好他還有一張免費的來回機票,因此他決定選定一個景點$P$,買好他居住地到$P$的來回機票,並規劃一個只由Tourist旅行社的新行程構成的路線,由一系列的行程構成,每一個行程的終點都是下一個行程的起點,第一個行程的起點和最後一個行程的終點都是$P$。而他要求至少要造訪2個景點,且除了景點$P$,卡爾不希望重複造訪任何景點。

卡爾希望能找到一個CP值最高的旅行路線。也就是說,他希望他的總花費除以造訪景點數量的值(平均景點花費)最小,不幸地,Tourist旅行社的行程並不一定能夠讓卡爾安排出一個符合條件的旅行方法。

例如,如果Tourist旅行社總共有6個行程包含5個景點,(起點, 終點, 價格)分別為(1, 3, 8), (1, 5, 4), (2, 3, 2), (3, 4, 5), (4, 1, 7), (5, 2, 6),則他可以選擇1->5->2->3->4->1的旅行方法,這樣總共花了4+6+2+5+7=24元並且遊覽了5個不同的景點,平均景點花費為$\frac{24}{5}$。這也是所有符合條件的旅行方法中平均景點花費最低的。
然而,如果Tourist旅行社總共有3個行程包含3個景點,(起點, 終點, 價格)分別為(1, 2, 6), (3, 1, 4), (3, 2, 2),那麼沒有任何一種旅行方法符合卡爾的條件。

對於給定的這些新行程,請問在卡爾要求的條件之下,他所規劃的旅行方法平均景點花費最低可以到多少,或者沒有任何旅行方法符合條件?

Input Format

本題為單筆輸入。
第一行有一個正整數$N$,代表總共有$N$個景點。
接下來有$N$行,每行有$N$個非負整數,第i行的第j個數為$A_{i,j}$。
若$A_{i,j}=0$,代表不存在從景點$i$到景點$j$的行程;否則代表存在一個從景點$i$到景點$j$的行程,要花$A_{i,j}$元。
保證不會有由$i$到$i$的行程,也就是$A_{i,i}=0$。

Output Format

如果存在符合條件的旅行方法,輸出一行包含兩個正整數$A,B$,以空白隔開,代表最低的平均景點花費的最簡分數表示為$\frac{A}{B}$。
如果不存在任何符合條件的旅行方法,則輸出一行-1 -1

Sample Input

輸入範例1:
3
0 6 0
0 0 0
4 2 0

輸入範例2:
5
0 0 8 0 4
0 0 2 0 0
0 0 0 5 0
7 0 0 0 0
0 6 0 0 0

Sample Output

輸出範例1:
-1 -1

輸出範例2:
24 5

Hints

本題共有五組測試資料。每組可有多個輸入檔案,全部答對該組才得分。

第一組13分,$N\leq 10, A_{i,j}\leq 10^ 9$。
第二組21分,$N\leq 100, A_{i,j}\leq 10^ 9$。
第三組9分,$N\leq 1000$,且存在正整數$k\leq 10^ 9$,使得對於所有的$i,j$,$A_{i,j}=0$或$A_{i,j}=k$。
第四組14分,$N\leq 1000, A_{i,j}\leq 10^ 9$,且行程總數量不超過$N+50$。
第五組43分,$N\leq 1000, A_{i,j}\leq 10^ 9$。

注意事項:
使用C++作答的同學,請在程式碼開頭加上#include<cstdio>,並利用scanf讀入資料。使用cin讀入資料可能會因為效率太差以致於程式執行時間超過限制。
scanf 常用的讀入方式如下:
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。

Problem Source

Problem Set / Description by Yihda Yol
建國中學105學年度全國賽模擬賽pE

Subtasks

No. Testdata Range Score
1 0~3 13
2 0~6 21
3 7~9 9
4 10~12 14
5 0~16 43

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 4000 65536 262144 1 2 5
1 4000 65536 262144 1 2 5
2 4000 65536 262144 1 2 5
3 4000 65536 262144 1 2 5
4 4000 65536 262144 2 5
5 4000 65536 262144 2 5
6 4000 65536 262144 2 5
7 4000 65536 262144 3 5
8 4000 65536 262144 3 5
9 4000 65536 262144 3 5
10 4000 65536 262144 4 5
11 4000 65536 262144 4 5
12 4000 65536 262144 4 5
13 4000 65536 262144 5
14 4000 65536 262144 5
15 4000 65536 262144 5
16 4000 65536 262144 5