1934 . 旅行社大特價

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

81.0% (17/21)

Submission's AC Ratio

13.4% (46/343)

Tags

CKsim 2016-CKsim-全國模擬

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個不同的景點，平均景點花費為245。這也是所有符合條件的旅行方法中平均景點花費最低的。
然而，如果Tourist旅行社總共有3個行程包含3個景點，(起點, 終點, 價格)分別為(1, 2, 6), (3, 1, 4), (3, 2, 2)，那麼沒有任何一種旅行方法符合卡爾的條件。

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

Input Format

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

Output Format

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

Sample Input 1

3
0 6 0
0 0 0
4 2 0

Sample Output 1

-1 -1

Sample Input 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 2

24 5

Hints

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

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

注意事項：
使用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 (VSS, 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
Submit out of contest
Back to Top