Orange Boy Can You Solve It Out? Ep.21.5
APPROXIMATE PROBLEM WARNING
Metro
There are N metro stations in a city. The distance between each two station is a fixed integer x. Your task is to construct some metro lines across the stations.
We define a cost from station A to station B as the minimum of these two rules:
 if we can reach B by hopping on some line of metro and hop off it after K stations, the cost is K*x
 if we can reach B by reaching station C with the cost of I, and we can reach B from C with the cost of J, then the cost is I+J+y where y is given.
Now there are A_{i,j} visitors want to reach station j from station i by metro.
The boss of the company gives you three requirements:
 "avg" the average cost of every visitor is as small as possible

"max" the maximum cost of every visitor is as small as possible

"mix" the average cost of the average cost of every visitor and the maximum cost of every visitor is as small as possible
Input
You are given the integer N(N<=1000) and the matrix A of size N*N. A_{i,j}\leq1000
You are given x and y too. (x,y<=1000)
Then you are given the requirement: "avg" "max" or "mix"
Output
Print the metro lines. You can use at most N lines.
Scoring
Your answer will be scored according to the requirement.
Example
Input
N=5
x=1,y=3
A={{0,0,0,0,1},{1,0,0,1,0},{1,1,1,1,1},{0,1,0,0,0},{1,0,0,0,0}}
(requirement is ignored)
Output
2 lines
line 1: 1 <> 3 <> 5
line 2: 2 <> 3 <> 4
Explain
the maximum cost is the visitor from 2 to 1, which is 1+1+3=5
the cost from 1 to 5 and 2 to 4 and vice versa is 2
the cost from 3 to 1/2/4/5 is 1
the cost from 3 to 3 is 0
版权声明：
作者：XGN
链接：https://blog.hellholestudios.top/archives/271
来源：Hell Hole Studios Blog
文章版权归作者所有，未经允许请勿转载。
共有 0 条评论