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
metro

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/271
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>