Problem F
Jumbled Journey
Together with some friends you are planning a holiday to the Beautiful Authentic Parks Centre. While there, you want to visit the parks as much as you can. As part of the preparation you, together with your best friend, decided to make an extensive map of the parks, the roads between them, and the lengths of these roads. To ensure that the visitors to the Parks Centre do not circle endlessly through the gorgeous parks, the routes between the parks are one-way only and are made such that it is impossible to visit a park more than once (that is, the corresponding graph is acyclic). Together you spend the entire day to create an incredibly detailed and admittedly rather large map of the Parks Centre.
![\includegraphics[width=0.9\textwidth ]{fig1.pdf}](/problems/jumbledjourney/file/statement/en/img-0001.png)
The next day disaster strikes: your friend happily announces that he got rid of the cumbersome map! Instead, he decided to replace it with a simple table containing only the average distances between the parks, weighing each route equally. Thus, he would give you an average distance of $8$ between park $1$ and park $4$ as in figure 1, because there are $3$ paths and their average length is $(6+8+10)/3=8$. You feel defeated, and you dread the thought of making the map all over again. Perhaps it might be easier to try and use the table of average distances your friend made in order to reconstruct the original map. One thing you remember, is that the roads on the map were never inefficient. If there was a direct road between two parks, then every path via at least one other park was strictly longer. This condition holds for the first sample input because, for example, the road from $1$ to $4$ has length $6$, which is shorter than the length of any other path from $1$ to $4$.
Given an input of average distances between parks, output the original map: a weighted directed acyclic graph for which these average distances hold.
Input
-
The first line contains an integer $1\leq n\leq 100$, the number of vertices (parks).
-
The next $n$ lines contain the average distance from vertex $i$ to vertex $j$ as the $j$th number on the $i$th line, or $-1$ in case there is no path from vertex $i$ to vertex $j$. All distances are either $-1$ or non-negative integers, at most $10^{15}$.
You know the following facts about the map (the original graph):
-
There is no way to follow the roads and return to a park once you have left it. That is, the graph is acyclic.
-
The lengths of the roads in the original graph are all integers.
-
Between any two parks, there are at most $1\, 000$ distinct paths you can take from one to the other.
-
Direct roads are always efficient: if there is a direct road from park $i$ to park $j$, every other path from $i$ to $j$ is strictly longer than that direct road.
Output
Print $n$ lines each containing $n$ integers. The $j$th number on the $i$th line should be the positive length of the edge from vertex $i$ to vertex $j$, or $-1$ if there is no such edge. It is guaranteed that a solution exists.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 0 2 5 8 -1 0 4 8 -1 -1 0 4 -1 -1 -1 0 |
-1 2 4 6 -1 -1 4 -1 -1 -1 -1 4 -1 -1 -1 -1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 0 -1 48 -1 132 -1 24 0 84 36 153 108 -1 -1 0 -1 84 -1 -1 -1 60 0 116 72 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 96 0 |
-1 -1 48 -1 -1 -1 24 -1 -1 36 -1 -1 -1 -1 -1 -1 84 -1 -1 -1 60 -1 36 72 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 96 -1 |
