TopCoder

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

User's AC Ratio

77.8% (7/9)

Submission's AC Ratio

26.3% (25/95)

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

For Testdata: 0 ~ 3, Score: 13
For Testdata: 0 ~ 6, Score: 21
For Testdata: 7 ~ 9, Score: 9
For Testdata: 10 ~ 12, Score: 14
For Testdata: 0 ~ 16, Score: 43
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 4000 65536 262144
1 4000 65536 262144
2 4000 65536 262144
3 4000 65536 262144
4 4000 65536 262144
5 4000 65536 262144
6 4000 65536 262144
7 4000 65536 262144
8 4000 65536 262144
9 4000 65536 262144
10 4000 65536 262144
11 4000 65536 262144
12 4000 65536 262144
13 4000 65536 262144
14 4000 65536 262144
15 4000 65536 262144
16 4000 65536 262144