Floyd's algorithm

Given a directed graph whose edges are assigned some non-negative weights (lengths). We need to find two vertices, the shortest path between which has the greatest length.

 

The first line contains the number of vertices N ≤50. Next comes the adjacency matrix of the graph, that is, N rows, each of which contains N numbers. The j-th number in the i-th row of the adjacency matrix specifies the length of the edge leading from the i-th vertex to the j-th one. Lengths can take any value from 0 to 1000000. It is guaranteed that there are zeros on the main diagonal of the matrix.

 

Print a single number – the length of the desired path.

Examples

#	Input	Output
1	3 0 7 3 7 0 10 2 215 0	10

Given a directed graph. You want to determine if it contains a cycle.

 

The first line contains the number of vertices N≤ 50. Next, N lines are followed by N numbers, each of which – 0 or 1. The j-th number in the i-th row is equal to 1 if and only if there is an edge going from the i-th vertex to the j-th one. It is guaranteed that there will be zeros on the diagonal of the matrix.

 

Print 0 if there is no cycle in the given graph, and 1 if there is one.

Examples

#	Input	Output
1	3 0 1 0 0 0 1 0 0 0	0
2	3 0 1 0 0 0 1 1 0 0	1

Given a directed graph. Determine if it has a negative weight cycle, and if so, output it.

 

The first line contains the number N (1 <= N <= 100) – the number of graph vertices. The next N lines contain N numbers each – graph adjacency matrix. Edge weights modulo less than 100000. If there is no edge, the corresponding value is 100000.

 

On the first line print "YES" if the cycle exists, or "NO" otherwise. If there is a loop, in the second line print the number of vertices in it (counting the same – first and last), and in the third line – the vertices included in this cycle are in traversal order. If there are several cycles, then  print any of them.

Examples

#	Input	Output
1	3 100000 100000 -51 100  100000 100000 100000 -50  100000	YES 4 3 2 1 3

The treasure hunter Vasya came across a map of an ancient dungeon. The dungeon is an NM size maze (1NM100 , NM100). Each cell of the labyrinth is either empty and traversable, or contains a wall. You can only move from a cell to a cell adjacent to the wall (for example, each cell can have no more than 4 adjacent cells).

 

In one of the cells there is a treasure that Vasya wants to get. The labyrinth has K entrances from which Vasya can start his journey.

 

It is required to determine from which entrance Vasya needs to start his journey so that the distance traveled to the treasure is the least. If there are several such inputs, print the input with the smallest number.

 

The first line contains 2 numbers N and M, which define the dimensions of the maze. The description of the labyrinth follows: N lines with M characters each. 0 means that the cell is free; 1 that there is a wall in the cage. The symbol * denotes a cell with a treasure (there is exactly one such cell in the labyrinth).

 

The (N+2)th line contains the number K (1<=K<= NxM) -- the number of entrances to the labyrinth. Next, K lines contain the coordinates of the inputs. Thus, the i-th line contains numbers xi and yi, meaning that the i-th input is located in the xi-th line and in the yi-th column (1xiN1yiM). It is guaranteed that the coordinates of the inputs are pairwise different, and that all the inputs are located in empty cells. None of the entrances are in the treasure cage.

 

It is necessary to display one number - the desired input number (numbering starts from 1). If the treasure cannot be reached, print -1.

Examples

#	Input	Output
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	1
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

You are given a directed weighted graph. Using its adjacency matrix, you need to determine for each pair of vertices whether there is a shortest path between them or not.

 

Comment: The shortest path may not exist for two reasons:

The first line of the input file contains a single number: N (1 <=N <=100) — the number of graph vertices. The next N lines contain N numbers each — adjacency matrix of the graph (the j-th number in the i-th line corresponds to the weight of the edge from vertex i to vertex j): the number 0 means no edge, and any other number — the presence of an edge of the corresponding weight. All modulo numbers do not exceed 100.

 

Print N lines of N numbers. The j-th number in the i-th line must correspond to the shortest path from vertex i to vertex j. The number should be 0 if there is no path, 1 if there is a shortest path, and 2 if there are paths but there are paths of arbitrarily small weight.

Examples

#	Input	Output
1	5 0 1 2 0 0 1 0 3 0 0 2 3 0 0 0 0 0 0 0 -1 0 0 0 -1 0	1 1 1 0 0  1 1 1 0 0  1 1 1 0 0  0 0 0 2 2  0 0 0 2 2

In the MMORPG "Space Traders Online" the speed of the player's movement between the stars is limited to one parsec per second. At this speed, you can quickly get to the nearest stars, but it can take several hours to travel from one end of the galaxy to the other. To speed up such long journeys, the creators of the game made several "wormholes" — tunnels connecting two points in space, which allow you to instantly move back and forth between these points.

Write a program that calculates the minimum travel time using wormhole information.

The first input line contains an integer N (1 ≤ N ≤ 100). This is followed by a line containing 6 integers — coordinates of start (x_s,y_s,z_s) and end (x_t,y _t,z_t) travel points. This is followed by N lines containing 6 integers — coordinates of the ends of "wormholes". All coordinates are measured in parsecs and are in the range from 0 to 10000, and there are no points with the same coordinates.

Print the minimum travel time in seconds with a precision of at least 10⁻⁶.
Examples

#	Input	Output
1	1 0 0 0 100 100 0 1 1 1 50 100 10	52.722246

Given an undirected weighted graph with negative weights, it is necessary to output information about the shortest path between 2 vertices.

Input
The first line contains an integer n - the number of vertices in the graph. Next, the input is an adjacency matrix, in which -1 means the absence of an edge between the vertices. After the matrix there is a number k - the number of requests, the next k lines contain 2 numbers each, a and b - vertices in request.

Imprint
The string must contain k numbers - the distance between a pair of numbers from the query in the order they are entered, if it is impossible to get from the top a to the top b, then output Imp.

You are given a directed complete graph with some weights (lengths) assigned to its edges. Weights can be positive, negative or zero. We are interested in the minimum length of all possible paths between all pairs of distinct vertices in this graph. It will be necessary to find out if this minimum exists, and if it does, calculate it. (There is no minimum if it is possible to find a path of negative length in the graph, arbitrarily large in absolute value, tending to infinity).

 

The first line is N≤50 vertices. Next comes the adjacency matrix of the graph, that is, N rows, each of which contains N numbers. The j-th number in the i-th row of the adjacency matrix specifies the length of the edge leading from the i-th vertex to the j-th one. Lengths can take any value from -1000000 to 1000000. It is guaranteed that there are zeros on the main diagonal of the matrix.

 

Print a single number – desired minimum. If it doesn't exist, output  -1.
Examples

#	Input	Output
1	3 0 42 18468  6335 0 26501  19170 15725 0	42
2	3 0 -7 3 -2 0 10 2 215 0	-1

Given a directed graph. Determine if it has a negative weight cycle.

Input

The first line contains the number N (1 <= N <= 100) – the number of graph vertices. The next N lines contain N numbers each – graph adjacency matrix. Edge weights modulo less than 100000. If there is no edge, the corresponding value is 100000.

 

On the first line print "YES" if the cycle exists, or "NO" otherwise. 

Examples

#	Input	Output
1	3 100000 100000 -51 100  100000 100000 100000 -50  100000	YES