e-olymp 2471. От матрицы смежности к списку рёбер

26/12/2018 by Андрей Лисовой

Задача

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка рeбер.

Вводные данные

Первая строка содержит количество вершин $n$ $(1 \leq n \leq 100)$ в графе. Затем идут $n$ строк по $n$ элементов в каждой — описание матрицы смежности.

Выходные данные

Вывести список ребер, упорядоченный по первой вершине в паре вершин, которая описывает ребро.

Тесты

Входные данные	Выходные данные
$3$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$	$1$ $2$ $1$ $3$ $2$ $3$
$3$ $0$ $1$ $0$ $1$ $0$ $0$ $0$ $0$ $0$	$1$ $2$
$5$ $0$ $1$ $0$ $1$ $1$ $1$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$	$1$ $2$ $1$ $4$ $1$ $5$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[][] x = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				x[i][j] = in.nextInt();
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				if(x[i][j] == 1) System.out.println((i+1) + " " + (j+1));
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[][] x = new int[n][n];

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

x[i][j] = in.nextInt();

}

for(int i = 0; i < n; i++) {

for(int j = i; j < n; j++) {

if(x[i][j] == 1) System.out.println((i+1) + " " + (j+1));

}

Решение задачи

Для решения задачи вводим матрицу смежности. Далее в цикле проходим верхнюю треугольную часть матрицы смежности и выписываем индексы (из какой вершины и в какую другую вершину идет ребро, т.е. получаем список ребер). Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 977. Дерево?

26/12/2018 by Костя Григорян

Задача

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.

Входные данные

Первая строка содержит количество вершин графа $n \left (1 \leq n \leq 100 \right).$ Далее записана матрица смежности размером $n × n$, в которой $1$ обозначает наличие ребра, $0$ — его отсутствие. Матрица симметрична относительно главной диагонали.

Выходные данные

Выведите сообщение YES, если граф является деревом, и NO в противном случае.

Тесты

Входные данные	Выходные данные
[latex]3 \\ 0 \ 1 \ 0 \\ 1 \ 0 \ 1 \\ 0 \ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]2 \\ 0 \ 1 \\ 1 \ 0[/latex]	[latex]YES[/latex]
[latex]4 \\ 0 \ 0 \ 0 \ 1 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 1 \ 0 \ 0 \ 0[/latex]	[latex]NO[/latex]
[latex]1 \\ 0[/latex]	[latex]YES[/latex]

Код программы

import java.util.Scanner;
import java.util.ArrayList;

class Main
{
	private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) {
		A[v]++;
		if (A[v]>1)
			return;
		for (int i=0; i<g.get(v).size(); i++)
		{
			if (g.get(v).get(i)!=p)
				dfs(g.get(v).get(i), v, g, A);
		}
	}
	
	public static void main (String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] A = new int[n];
		ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
		for (int i=0; i<n; i++) {
			ArrayList<Integer> r = new ArrayList<Integer>();
			for (int j=0; j<n; j++) {
				int a = scanner.nextInt();
				if (a==1) {
					r.add(j);
				}
			}
			g.add(r);
		}
		int t=0;
		dfs(0, -1, g, A);
		for (int i=0; i<n; i++)
		{
			if (A[i]!=1)
			{
				t++;
				break;
			}
		}
		if (t!=0)
			System.out.print("NO");
		else
			System.out.print("YES");
	}
}

import java.util.Scanner;

import java.util.ArrayList;

class Main

{

private static void dfs(int v, int p, ArrayList<ArrayList<Integer>> g , int[] A) {

A[v]++;

if (A[v]>1)

return;

for (int i=0; i<g.get(v).size(); i++)

{

if (g.get(v).get(i)!=p)

dfs(g.get(v).get(i), v, g, A);

}

public static void main (String[] args)

{

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int[] A = new int[n];

ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();

for (int i=0; i<n; i++) {

ArrayList<Integer> r = new ArrayList<Integer>();

for (int j=0; j<n; j++) {

int a = scanner.nextInt();

if (a==1) {

r.add(j);

}

g.add(r);

}

int t=0;

dfs(0, -1, g, A);

for (int i=0; i<n; i++)

{

if (A[i]!=1)

{

t++;

break;

}

if (t!=0)

System.out.print("NO");

else

System.out.print("YES");

}

Решение задачи

Считываем граф в ArrayList<ArrayList>. Далее выбираем любую вершину и запускаем из нее своего рода dfs. Заключается он в том, что мы идем к потомкам текущей вершины, попутно смотря были ли мы здесь. Если были, завершаем процесс, так как мы нашли цикл (граф, содержащий цикл, не является деревом). При этом мы не идем от потомка к предку. В конце проверяем обошли ли мы все вершины и не встречались ли нам циклы.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 5080. Количество висячих вершин 1

25/12/2018 by Карина Миловская

Задача

Дан простой неориентированный невзвешенный граф. Подсчитать количество висячих вершин в нем. Вершина называется висячей, если ее степень равна $1.$

Входные данные

В первой строке находится число $n$ $\left ( 1 \leq n \leq 1000 \right ).$ В следующих $n$ строках находится матрица смежности.

Выходные данные

Выведите количество висячих вершин в графе.

Тесты

Входные данные	Выходные данные
$2 \\ 0 \ 1 \\ 1 \ 0$	$2$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 1 \ 0$	$0$
$4 \\ 1 \ 0 \ 0 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 0 \ 0 \ 1$	$4$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 0 \ 0$	$1$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int [][] gr = new int [1001][1001]; 
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(); 
		int ans = 0; 
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				gr[i][j] =  in.nextInt(); 
			}
		}
		for (int i=0; i<n; i++) {
			int cnt = 0; 
			for (int j=0; j<n; j++) {
				if (gr[i][j] == 1) cnt++;
			}
			if (cnt==1) ans++;
		}
		System.out.println(ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

int [][] gr = new int [1001][1001];

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int ans = 0;

for (int i=0; i<n; i++) {

for (int j=0; j<n; j++) {

gr[i][j] = in.nextInt();

}

for (int i=0; i<n; i++) {

int cnt = 0;

for (int j=0; j<n; j++) {

if (gr[i][j] == 1) cnt++;

}

if (cnt==1) ans++;

}

System.out.println(ans);

}

Решение

Введем обозначения: $gr$ – имя массива(матрицы смежности), $n$ – количество вершин, $cnt$ – счётчик.
Просматривая матрицу смежности, подсчитываем количество единиц, т.е количество инцидентных вершин данной вершине. Инцидентные вершины — вершины, которые соединены ребром. Степенью вершины называется количество рёбер, инцидентных этой вершине. Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице только одна единица, то вершина имеет степень 1 и является висячей.
Сперва предположим, что что граф не имеет висячих вершин, далее введём матрицу смежности, подсчитаем степень вершины и проверим, является ли вершина висячей. В ответе выводим количество висячих вершин в графе.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

e-olimp 5079. Транзитивность ориентированного графа

25/12/2018 by Саша Рябова

Условие

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин $u$, $v$ и $w$ из того, что из $u$ в вершину $v$ ведет ребро и из вершины $v$ в вершину $w$ ведет ребро, следует, что из вершины $u$ в вершину $w$ ведет ребро.
Проверьте, что заданный ориентированный граф является транизитивным.

Входные данные

Входной файл содержит число $n (1 \leq n \leq 100)$ — число вершин в графе, и затем $n$ строк по $n$ чисел, каждое из которых равно $0$ или $1$ — его матрицу смежности.

Выходные данные

Выведите в выходной файл YES, если граф является транзитивным, и NO — в противном случае.

Тесты

Входные данные	Выходные данные
$3$ $0$ $1$ $1$ $0$ $0$ $1$ $0$ $0$ $0$	YES
$3$ $0$ $1$ $1$ $1$ $0$ $0$ $0$ $1$ $0$	NO

Код задачи

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String answer = "YES";
        short[][] graph = new short [n][n];
        for (int i = 0; i < n; i++) {
            for( int j = 0; j < n; j++) {
                graph[i][j] = sc.nextShort();
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if (graph[i][j] == 1){ 
                    for (int z = 0; z < n; z++){
                        if (graph[j][z] == 1 && graph[i][z] == 0) { 
                            answer = "NO";
                            break;
                        }   
                    }   
                }
            }
        }
    System.out.print(answer);
    }
}

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

String answer = "YES";

short[][] graph = new short [n][n];

for (int i = 0; i < n; i++) {

for( int j = 0; j < n; j++) {

graph[i][j] = sc.nextShort();

}

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

if (graph[i][j] == 1){

for (int z = 0; z < n; z++){

if (graph[j][z] == 1 && graph[i][z] == 0) {

answer = "NO";

break;

}

System.out.print(answer);

}

Решение

Представим матрицу смежности графа в виде двумерного массива. Тогда, если $graph[i][j]=1$, то из вершины $i$ в вершину $j$ ведёт ребро. Проверяем с помощью циклов транзитивность графа, то есть если из вершины $i$ в вершину $j$ ведёт ребро и из вершины $j$ в вершину $z$, то граф транзитивен, если есть ребро $graph[i][z]$.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 1108. Червячные дыры

23/12/2018 by Алиса Ворохта

Задача

В $2163$ году были обнаружены червячные дыры. Червячная дыра представляет собой тоннель сквозь пространство и время, соединяющий две звездные системы. Эти дыры имеют следующие свойства:

Червячные дыры являются односторонними.
Время путешествия по любому тоннелю равно нулю.
Червячная дыра имеет два конца, каждый из которых находится в звездной системе.
Звездная система в своих границах может иметь несколько концов червячных дыр.
По некоторой неизвестной причине начиная с нашей Солнечной системы всегда можно достигнуть любую другу звездную систему перемещаясь некоторой последовательностью червячных дыр (возможно, это потому что Земля является центром универсума).
Между любой парой звездных систем существует не более одной червячной дыры в любом из направлений.
Оба конца червячной дыры не могут находиться в одной звездной системе.
Каждая червячная дыра перемещает путешественника на определенное константное количество лет вперед или назад. Например, одна дыра может переместить на $15$ лет в будущее, а другая на $42$ года в прошлое.

Известный физик, живущий на Земле, хочет использовать червячные дыры для исследования теории Большого Взрыва. Поскольку двигатель искривления пространства еще не изобретен, невозможно напрямую путешествовать между звездными системами. Однако это можно делать при помощи червячных дыр.

Ученый хочет достигнуть цикла червячных дыр, который поможет ему попасть в прошлое. Двигаясь по этому циклу несколько раз, можно прийти ко времени, когда имел место Большой Взрыв и наблюдать его собственными глазами. Напишите программу, которая определяет существование такого цикла.

Входные данные

Первая строка содержит количество звездных систем $n$ $(1 ≤ n ≤ 1000)$ и количество червячных дыр $m$ $(0 ≤ m ≤ 2000)$. Звездные системы пронумерованы от $0$ (наша солнечная система) до $n — 1$. Каждая червячная дыра описывается в отдельной строке и содержит три целых числа $x$, $y$ и $t$. Эти числа указывают на возможность передвижения из звездной системы с номером $x$ в звездную систему с номером $y$, при этом время изменяется на $t$ $(-1000 ≤ t ≤ 1000)$ лет.

Выходные данные

Cтрока содержит информацию, возможно ли в заданном множестве систем попасть в минус бесконечность во времени используя червячные дыры. Выводить следует строку «possible» или «not possible».

Тесты

Входные данные	Выходные данные
$3$ $3$ $0$ $1$ $1000$ $1$ $2$ $15$ $2$ $1$ $-42$	possible
$4$ $4$ $0$ $1$ $10$ $1$ $2$ $20$ $2$ $3$ $30$ $3$ $0$ $-60$	not possible
$3$ $3$ $0$ $1$ $-100$ $1$ $2$ $1$ $2$ $1$ $0$	not possible

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	private static class Node {
        private int x;
        private int y;
        private int t;
 
        private Node(int x, int y, int t) {
            this.x = x;
            this.y = y;
            this.t = t;
        }
    }
	public static void main (String[] args) throws java.lang.Exception
	{
    	Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		Node r = null;
		Node[] canals = new Node[m + 1];
		for (int i = 0; i < m; i++) {
        	int x = in.nextInt();
			int y = in.nextInt();
			int t = in.nextInt();
			r = new Node(x, y, t);
        	canals[i] = r;
		}
		int INF = 2000000;
		int[] distance = new int[n + 1];
		int subs = -1;
		for (int i = 0; i < n; i++) {
        	subs = -1;
        	for (int j = 0; j  distance[canals[j].x] + canals[j].t) {
                	distance[canals[j].y] = Math.max (-INF, distance[canals[j].x] + canals[j].t);
                	subs = canals[j].y;
            	}
            }
    	}
    	if (subs == -1) {
    		System.out.println("not possible");
    	}
    	else {
        	System.out.println("possible");
    	}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

private static class Node {

private int x;

private int y;

private int t;

private Node(int x, int y, int t) {

this.x = x;

this.y = y;

this.t = t;

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int m = in.nextInt();

Node r = null;

Node[] canals = new Node[m + 1];

for (int i = 0; i < m; i++) {

int x = in.nextInt();

int y = in.nextInt();

int t = in.nextInt();

r = new Node(x, y, t);

canals[i] = r;

}

int INF = 2000000;

int[] distance = new int[n + 1];

int subs = -1;

for (int i = 0; i < n; i++) {

subs = -1;

for (int j = 0; j distance[canals[j].x] + canals[j].t) {

distance[canals[j].y] = Math.max (-INF, distance[canals[j].x] + canals[j].t);

subs = canals[j].y;

}

if (subs == -1) {

System.out.println("not possible");

}

else {

System.out.println("possible");

}

Описание решения

Решение данной задачи сводится к нахождению отрицательного цикла в ориентированном графе. Необходимо воспользоваться алгоритмом Форда-Беллмана.
Создадим массив на $n$ элементов и заполним его нулями. Алгоритм основан на том, что если в графе размерностью $n$ элементов нет отрицательных циклов, то после $n-1$ прохождения изменения в массиве кратчайших расстояний не будет. Поэтому, будем выполнять следующее $n$ раз:

Возьмем первое ребро из массива $canals$, и проведем сравнение: если исходная длина пути конца данного ребра из исходного массива $distance$ больше, чем сумма длины пути начала массива и стоимости прохода по данному ребру $canals[].t$, то изменим в массиве $distance$ элемент с номером конца исходного ребра, и изменим индикатор изменений $subs$, чтобы показать, что в ходе данного прохода были внесены изменения.
Переходим к следующему ребру.

Если после во время последнего прохода ни разу не была изменена переменная $subs$, то это значит, что в графе нет циклов отрицательной длины, и тогда выводим «not possible». Иначе, выводим «possible».

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 88. Месть Ли Чака

15/10/2018 by Кирилл Волков

Задача

“Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш участвовал в другом приключении и серьезно нуждается в Вашей помощи, потому что на этот раз это вопрос жизни и смерти. Наш Гайбраш в последнем приключении приплыл на таинственный остров (ТО), чтобы найти подсказку для еще более таинственного сокровища. Тем временем Ли Чак узнал об этой поездке и подготовил ловушку Гайбрашу на ТО. ТО имеет прямоугольную форму (поскольку мы знаем, что он таинственный) и его карта может рассматриваться как матрица такой же размерности. Назовем каждый элемент матрицы участком. Некоторые участки могут быть заполнены горными скалами. Такие участки считаются непроходимыми.

Рассмотрим остров, карта которого изображена на рисунке. Эта карта представляет собой матрицу с $6$ строками и $7$ столбцами. Комнаты «R» показывают участки со скалами. Гайбраш должен начинать с участка, отмеченного «g», а Ли Чак – с участка «l». У Гайбраша есть шанс сбежать с этого проклятого острова, если он достигнет конечного участка, который отмечен символом «e» на карте. Каждую единицу времени Гайбраш может пойти на соседний с текущим участок по горизонтали или вертикали (но не по диагонали), если в нем нет скал, или не двигаться. То есть он может переместиться на один участок вверх, вниз, влево, вправо или вообще остаться на месте. В приведенном примере Гайбраш в первый момент времени может остаться или пойти в комнату слева от него. Все указанные правила применяются также и к движению Ли Чака, но с одним исключением: он не может войти на конечный участок (отмеченный «e»). То есть, каждую единицу времени Ли Чак может пойти на один участок вверх, вниз, влево, вправо (если только это не «R» или «e») или стоять. Мы предполагаем, что каждую единицу времени сначала делает ход (или стоит) Гайбраш, а затем ходит (или стоит) Ли Чак, в следующую единицу времени опять сначала Гайбраш, затем Ли Чак и так далее. Если Гайбраш и Ли Чак встретятся на одном участке, то Ли Чак немедленно убьет нашего бедного Гайбраша.

Ваша задача состоит в том, чтобы узнать, есть ли по крайней мере один безопасный путь или нет. Безопасный путь – это путь для Гайбраша (от «g» до «e») такой, что Ли Чак не может поймать Гайбраша на этом пути независимо от того, что он (Ли Чак) делает каждую единицу времени.

Входные данные

Первая строка входа содержит единственное целое число — количество тестовых случаев. Далее идут строки данных для тестовых случаев. Каждый тест начинается со строки, содержащей два целых числа $R$ и $C$ ($4 \leq R, C \leq 30$), которые обозначают количество строк и столбцов карты таинственного острова соответственно. Далее следуют $R$ строк, каждая содержит $C$ символов, представляющих карту. Есть единственные отметки «g», «l» и «e» на карте.

Выходные данные

Для каждого теста необходимо вывести единственную строку. Если существует, по крайней мере, хотя бы один безопасный путь для тестового случая, должно быть выведено слово «YES», и слово «NO», если такого пути нет. Предполагается, что если существует безопасный путь, то необходимо не более $1000$ единиц времени для прохождения по нему Гайбраша.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

Код программы

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main{

    private static class Node {
        private int i;
        private int j;

        private Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    private static void fill(int[][] a, int value) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                a[i][j] = value;
            }
        }
    }

    private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        moves[start.i][start.j] = 0;
        queue.add(start);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
    }

    private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(start);
        moves[start.i][start.j] = 0;
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int i = curNode.i;
            int j = curNode.j;
            if (map[i][j] == 'e') {
                return true;
            }
            if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {
                moves[i - 1][j] = moves[i][j] + 1;
                queue.add(new Node(i - 1, j));
            }
            if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {
                moves[i + 1][j] = moves[i][j] + 1;
                queue.add(new Node(i + 1, j));
            }
            if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {
                moves[i][j - 1] = moves[i][j] + 1;
                queue.add(new Node(i, j - 1));
            }
            if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {
                moves[i][j + 1] = moves[i][j] + 1;
                queue.add(new Node(i, j + 1));
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int tests = Integer.parseInt(bufferedReader.readLine());
        for (int r = 0; r < tests; r++) {
            String[] sizes = bufferedReader.readLine().split(" ");
            int n = Integer.parseInt(sizes[0]);
            int m = Integer.parseInt(sizes[1]);
            char[][] map = new char[n][m];
            Node g = null;
            Node l = null;
            Node e = null;
            for (int i = 0; i < n; i++) {
                map[i] = bufferedReader.readLine().toCharArray();
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == 'g') {
                        g = new Node(i, j);
                    }
                    else if (map[i][j] == 'l') {
                        l = new Node(i, j);
                    }
                    else if (map[i][j] == 'e') {
                        e = new Node(i, j);
                    }
                }
            }
            int[][] secondPlayerDistances = new int[n][m];
            fill(secondPlayerDistances, Integer.MAX_VALUE);
            bfsSecondPlayer(map, secondPlayerDistances, l);
            int[][] firstPlayerDistances = new int[n][m];
            fill(firstPlayerDistances, Integer.MAX_VALUE);
            boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);
            System.out.println(ok ? "YES" : "NO");
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

public class Main{

private static class Node {

private int i;

private int j;

private Node(int i, int j) {

this.i = i;

this.j = j;

}

private static void fill(int[][] a, int value) {

for (int i = 0; i < a.length; i++) {

for (int j = 0; j < a[i].length; j++) {

a[i][j] = value;

}

private static void bfsSecondPlayer(char[][] map, int[][] moves, Node start) {

Queue<Node> queue = new LinkedList<>();

moves[start.i][start.j] = 0;

queue.add(start);

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (i > 0 && map[i - 1][j] != 'R' && map[i - 1][j] != 'e' && moves[i][j] + 1 < moves[i - 1][j]) {

moves[i - 1][j] = moves[i][j] + 1;

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && map[i + 1][j] != 'e' && moves[i][j] + 1 < moves[i + 1][j]) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && map[i][j - 1] != 'e' && moves[i][j] + 1 < moves[i][j - 1]) {

moves[i][j - 1] = moves[i][j] + 1;

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && map[i][j + 1] != 'e' && moves[i][j] + 1 < moves[i][j + 1]) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

private static boolean bfsFirstPlayer(char[][] map, int[][] moves, int[][] secondPlayerMoves, Node start) {

Queue<Node> queue = new LinkedList<>();

queue.add(start);

moves[start.i][start.j] = 0;

while (!queue.isEmpty()) {

Node curNode = queue.poll();

int i = curNode.i;

int j = curNode.j;

if (map[i][j] == 'e') {

return true;

}

if (i > 0 && map[i - 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i - 1][j], secondPlayerMoves[i - 1][j])) {

moves[i - 1][j] = moves[i][j] + 1;

queue.add(new Node(i - 1, j));

}

if (i < moves.length - 1 && map[i + 1][j] != 'R' && moves[i][j] + 1 < Math.min(moves[i + 1][j], secondPlayerMoves[i + 1][j])) {

moves[i + 1][j] = moves[i][j] + 1;

queue.add(new Node(i + 1, j));

}

if (j > 0 && map[i][j - 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j - 1], secondPlayerMoves[i][j - 1])) {

moves[i][j - 1] = moves[i][j] + 1;

queue.add(new Node(i, j - 1));

}

if (i < moves[0].length - 1 && map[i][j + 1] != 'R' && moves[i][j] + 1 < Math.min(moves[i][j + 1], secondPlayerMoves[i][j + 1])) {

moves[i][j + 1] = moves[i][j] + 1;

queue.add(new Node(i, j + 1));

}

return false;

}

public static void main(String[] args) throws IOException{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

int tests = Integer.parseInt(bufferedReader.readLine());

for (int r = 0; r < tests; r++) {

String[] sizes = bufferedReader.readLine().split(" ");

int n = Integer.parseInt(sizes[0]);

int m = Integer.parseInt(sizes[1]);

char[][] map = new char[n][m];

Node g = null;

Node l = null;

Node e = null;

for (int i = 0; i < n; i++) {

map[i] = bufferedReader.readLine().toCharArray();

for (int j = 0; j < m; j++) {

if (map[i][j] == 'g') {

g = new Node(i, j);

}

else if (map[i][j] == 'l') {

l = new Node(i, j);

}

else if (map[i][j] == 'e') {

e = new Node(i, j);

}

int[][] secondPlayerDistances = new int[n][m];

fill(secondPlayerDistances, Integer.MAX_VALUE);

bfsSecondPlayer(map, secondPlayerDistances, l);

int[][] firstPlayerDistances = new int[n][m];

fill(firstPlayerDistances, Integer.MAX_VALUE);

boolean ok = bfsFirstPlayer(map, firstPlayerDistances, secondPlayerDistances, g);

System.out.println(ok ? "YES" : "NO");

}

Решение задачи

Представим карту острова в виде неориентированного графа, вершинами которого в случае Гайбраша являются все участки, кроме участков с пометкой «R», а для Ли Чака — все участки, кроме участков с пометками «R» и «e». Две вершины будут соединяться ребром, если они соответствуют участкам, имеющим общую сторону. Обозначим начальное местоположение Гайбраша — $g,$ Ли Чака — $l.$, выход $e.$
Безопасный для Гайбраша маршрут существует тогда и только тогда, когда существует путь $\omega,$ такой, что для $\forall v \in \omega \ \rho \left(g, v \right ) + 1 < \rho(l, v).$ С помощью поиска в ширину найдем минимальное количество шагов, за которое Ли Чак попадает в каждую клетку, в которую он может попасть. Аналогично реализуем поиск в ширину для Гайбраша с той лишь разницей, что Гайбраш должен миновать те вершины графа, в которые он будет добираться дольше, чем Ли Чак. Если при этом найдется путь, соединяющий вершину, соответствующую начальному местоположению Гайбраша с вершиной, соответствующую цели, то он сможет спастись, в противном случае — нет.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

e-olymp 1388. Заправки

16/12/2017 by Эммануил Прокопов

Задача с сайта e-olymp.com.

Условие задачи

В стране n городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в n-ый, потратив как можно меньшее количество денег.

Входные данные

Сначала идет количество городов n (1 ≤ n ≤ 100), затем идет n чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Затем идет количество дорог m в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

Выходные данные

Выведите одно число — суммарную стоимость маршрута или -1, если добраться невозможно.

Тесты

№	Входные данные	Выходные данные
1	4 1 10 2 15 4 1 2 1 3 4 2 4 3	3
2	4 1 10 2 15 0	-1
3	5 1 2 3 4 5 4 1 2 2 3 3 4 4 5	10

Код программы

import java.util.*;

class Main
{
	//Условная бесконечность
	public static final int INF = 1000000;
	
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		int n, m, curFrom, curTo;
		n = input.nextInt();
		
		int price[] = new int[n+1];     //Цены на бензин в i-ом городе
		int distance[] = new int[n+1];  //Минимальные затраты на то, чтобы обраться до i-го города
		boolean used[] = new boolean[n+1]; //Был ли рассмотрен этот город?
		Vector <Integer> graph[] = new Vector[n+1];
		for (int i = 1; i <= n; ++i) {
			price[i] = input.nextInt();
			distance[i] = INF;
			used[i] = false;
			graph[i] = new Vector();
		}
		//Заполнение списка смежности
		m = input.nextInt();
		for (int i = 0; i < m; ++i) {
			curFrom = input.nextInt();
			curTo = input.nextInt();
			graph[curFrom].add(curTo);
			graph[curTo].add(curFrom);
		}
		//Нахождение оптимальной стоимости маршрута. На каждой итерации цикла находим город,
		//стоимость маршрута из начального города к которому минимальна. Если оказывается,
		//что эта стоимость бесконечна, значит, искомого пути не существует.
		distance[1] = 0;
		for(int i = 0; i < n; ++i) {
			int curCity = -1; //Город, рассматривыемый в данной итерации
			for (int j = 1; j <= n; ++j)
				if (!used[j] && (curCity == -1 || distance[j] < distance[curCity])) curCity = j;
			if (distance[curCity] == INF) break;
			used[curCity] = true;
			//Релаксация стоимости маршрута для всех городов, в которые можно попасти из данного
			for(int j = 0; j < graph[curCity].size(); ++j) {
				int to = graph[curCity].elementAt(j); 
				distance[to] = Math.min(distance[to], distance[curCity] + price[curCity]);
			}
		}
		//Вывод ответа
		System.out.print(distance[n] == INF ? -1 : distance[n]);
	}
}

import java.util.*;

class Main

{

//Условная бесконечность

public static final int INF = 1000000;

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

int n, m, curFrom, curTo;

n = input.nextInt();

int price[] = new int[n+1]; //Цены на бензин в i-ом городе

int distance[] = new int[n+1]; //Минимальные затраты на то, чтобы обраться до i-го города

boolean used[] = new boolean[n+1]; //Был ли рассмотрен этот город?

Vector <Integer> graph[] = new Vector[n+1];

for (int i = 1; i <= n; ++i) {

price[i] = input.nextInt();

distance[i] = INF;

used[i] = false;

graph[i] = new Vector();

}

//Заполнение списка смежности

m = input.nextInt();

for (int i = 0; i < m; ++i) {

curFrom = input.nextInt();

curTo = input.nextInt();

graph[curFrom].add(curTo);

graph[curTo].add(curFrom);

}

//Нахождение оптимальной стоимости маршрута. На каждой итерации цикла находим город,

//стоимость маршрута из начального города к которому минимальна. Если оказывается,

//что эта стоимость бесконечна, значит, искомого пути не существует.

distance[1] = 0;

for(int i = 0; i < n; ++i) {

int curCity = -1; //Город, рассматривыемый в данной итерации

for (int j = 1; j <= n; ++j)

if (!used[j] && (curCity == -1 || distance[j] < distance[curCity])) curCity = j;

if (distance[curCity] == INF) break;

used[curCity] = true;

//Релаксация стоимости маршрута для всех городов, в которые можно попасти из данного

for(int j = 0; j < graph[curCity].size(); ++j) {

int to = graph[curCity].elementAt(j);

distance[to] = Math.min(distance[to], distance[curCity] + price[curCity]);

}

//Вывод ответа

System.out.print(distance[n] == INF ? -1 : distance[n]);

}

Описание

Оптимальную стоимость маршрута будем находить по алгоритму Дейкстры. Цены на бензин в i-ом городе хранятся в массиве price. Минимальные стоимости маршрутов к каждому из городов хранятся в массиве distance, изначально все маршруты принимаем бесконечно дорогими. Кроме того, для хранения информации о том, был ли рассмотрен i-й город, используется массив used. Сам граф представляется в виде списка смежности. Для этого используется массив векторов <strong>graph</strong>. Если в итоге стоимость маршрута до целевого города осталась бесконечной, значит, пути к нему не существует, и выводится -1. Иначе выводится эта стоимость.

Код на ideone.com.

Засчитанное решение на e-olymp.com.

e-olymp 5072. Подсчет количества ребер

06/07/2017 by Присяжный Михаил

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

Входные данные:

Входной файл содержит число [latex]n(1 \leq n \leq 100)[/latex] — число вершин в графе, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — его матрицу смежности.

Выходные данные:

Выведите в выходной файл количество ребер заданного графа.

Тест

№	Значения	Результат
1	3 0 1 1 1 0 1 0 1 1	6

Решение

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static void main (String[] args)
	{
		int n;
    	Scanner sc =new Scanner(System.in);
    	n=sc.nextInt();
 		int k, l=0;
    	for(int i=0;i<n;i++){
        	for(int j=0; j<n; j++){
            	k=sc.nextInt();
            	if (k>0)
            	l++;
    		}
    	}
 		System.out.println(l);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args)

{

int n;

Scanner sc =new Scanner(System.in);

n=sc.nextInt();

int k, l=0;

for(int i=0;i<n;i++){

for(int j=0; j<n; j++){

k=sc.nextInt();

if (k>0)

l++;

}

System.out.println(l);

}

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную n типа int. Чтобы найти количество ребер в графе, вводим в двух циклах каждый элемент матрицы смежности и если значение больше нуля, то увеличиваем сумму.

e-olymp 975. Флойд

04/07/2017 by Шостак Дмитрий

Задача

Постановка задачи на e-olymp.

Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.

Входные данные

В первой строке содержится количество вершин графа [latex]n[/latex] [latex](1 \leq n \leq 100)[/latex]. В следующих [latex]n[/latex] строках находится по [latex]n[/latex] чисел, которые задают матрицу смежности графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.

Выходные данные

Вывести искомое максимальное кратчайшее расстояние.

Тесты

№	n	matrix	Результат
1	4	0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0	16
2	3	0 -1 2 2 0 -1 4 1 0	4
3	5	0 -1 -1 3 4 2 0 3 -1 4 -1 4 0 -1 4 3 -1 2 0 1 1 1 -1 -1 0	8

Ссылка на успешно пройденные тесты на сайте e-olymp.

Решение

import java.util.*;
public class Graph {

    public static void main(String[] args){
        Scanner input =  new Scanner(System.in);

        int n, max = 0;
        n = input.nextInt();
        int[][] matrix = new int[n][n];

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = input.nextInt();
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){
                        if(matrix[j][k] == -1)
                            matrix[j][k] = matrix[j][i] + matrix[i][k];
                        else
                            matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);
                    }
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] > max) max = matrix[i][j];
            }
        }

        System.out.println(max);
    }
}

import java.util.*;

public class Graph {

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int n, max = 0;

n = input.nextInt();

int[][] matrix = new int[n][n];

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

matrix[i][j] = input.nextInt();

}

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

for(int k = 0; k < n; k++){

if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){

if(matrix[j][k] == -1)

matrix[j][k] = matrix[j][i] + matrix[i][k];

else

matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);

}

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

if(matrix[i][j] > max) max = matrix[i][j];

}

System.out.println(max);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Данная задача решается при использовании алгоритма Флойда-Уоршелла, суть которого состоит в нахождении длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Код данного алгоритма можно наблюдать в цикле по [latex]i[/latex], в котором имеются два вложенных цикла по [latex]j[/latex] и по [latex]k[/latex]. Здесь мы проходим по элементам матрицы смежности графа, проверяя существует ли ребро между вершинами. Далее следуя алгоритму Флойда выполняем следующее действие — с помощью функции Math.min() находим минимальный путь из одной вершины в другую, записывая его в матрицу. По нахождении всех кратчайших путей, находим максимальный из них, и выводим его в консоль.

e-olymp 974. Флойд-1

01/11/2016 by Эдуард Брагар

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

В первой строке записано количество вершин графа n (1 ≤ [latex]n[/latex] ≤ 100). В следующих n строках записано по [latex]n[/latex] чисел — матрица смежности графа ([latex]j[/latex]-ое число в [latex]i[/latex]-ой строке соответствует весу ребра из вершины [latex]i[/latex] в вершину [latex]j[/latex]). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

Выходные данные

Выведите [latex]n[/latex] строк по [latex]n[/latex] чисел — матрицу кратчайших расстояний между парами вершин. [latex]j[/latex]-ое число в [latex]i[/latex]-ой строке должно равняться весу кратчайшего пути из вершины [latex]i[/latex] в вершину [latex]j[/latex].

Алгоритм

(взято с Википедии)

Пусть вершины графа [latex]{\displaystyle G=(V,\;E),\;|V|=n}[/latex] пронумерованы от 1 до [latex] {\displaystyle n}[/latex] и введено обозначение [latex]{\displaystyle d_{ij}^{k}}[/latex] для длины кратчайшего пути от [latex] {\displaystyle i}[/latex] до [latex]{\displaystyle j}[/latex], который кроме самих вершин [latex] {\displaystyle i,\;j} [/latex] проходит только через вершины [latex]{\displaystyle 1\ldots k} [/latex]. Очевидно, что [latex]{\displaystyle d_{ij}^{0}} [/latex] — длина (вес) ребра [latex]{\displaystyle (i,\;j)}[/latex], если таковое существует (в противном случае его длина может быть обозначена как [latex]{\displaystyle \infty } [/latex] ).

Существует два варианта значения [latex] {\displaystyle d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)} d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)[/latex]:

Кратчайший путь между [latex]{\displaystyle i,\;j}[/latex] не проходит через вершину [latex] {\displaystyle k}[/latex], тогда [latex]{\displaystyle d_{ij}^{k}=d_{ij}^{k-1}}[/latex] Существует более короткий путь между [latex]{\displaystyle i,\;j}[/latex], проходящий через [latex]{\displaystyle k}[/latex], тогда он сначала идёт от [latex]{\displaystyle i} [/latex] до [latex] {\displaystyle k} [/latex], а потом от [latex] {\displaystyle k} [/latex] до [latex] {\displaystyle j} [/latex]. В этом случае, очевидно, [latex]{\displaystyle d_{ij}^{k}=d_{ik}^{k-1}+d_{kj}^{k-1}}[/latex]

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

Тогда рекуррентная формула для [latex]{\displaystyle d_{ij}^{k}}[/latex] имеет вид:

[latex]{\displaystyle d_{ij}^{0}}[/latex] — длина ребра [latex] {\displaystyle (i,\;j);} (i,\;j);[/latex] [latex]{\displaystyle d_{ij}^{k}=\min(d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}).}[/latex]

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения [latex]{\displaystyle d_{ij}^{k},} [/latex], [latex]{\displaystyle \forall i,\;j}[/latex] для [latex] {\displaystyle k} [/latex] от 1 до [latex] {\displaystyle n} [/latex]. Полученные значения [latex] {\displaystyle d_{ij}^{n}}[/latex] являются длинами кратчайших путей между вершинами [latex]. {\displaystyle i,\;j.} [/latex].

Код

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;


class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
			Scanner in =new Scanner(System.in);
			int n = in.nextInt();
			int w[][] = new int[n][n];	 
			for( int i = 0 ; i < n ; i++ ){
				for( int j = 0 ; j < n ; j++ ){
					w[i][j] = in.nextInt();
				}
			}
	
			for( int k = 0 ; k < n ; k++ ){
				for( int i = 0 ; i<n ; i++ ){
					for( int j=0 ; j<n ; j++ ){
					    w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);
					}
				}
			}
    
			for( int i = 0 ; i < n ; i++ ){
				for( int j = 0 ; j < n ; j++ ){
		    		System.out.print(w[i][j] + " ");
				}
				System.out.println();
    		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in =new Scanner(System.in);

int n = in.nextInt();

int w[][] = new int[n][n];

for( int i = 0 ; i < n ; i++ ){

for( int j = 0 ; j < n ; j++ ){

w[i][j] = in.nextInt();

}

for( int k = 0 ; k < n ; k++ ){

for( int i = 0 ; i<n ; i++ ){

for( int j=0 ; j<n ; j++ ){

w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);

}

for( int i = 0 ; i < n ; i++ ){

for( int j = 0 ; j < n ; j++ ){

System.out.print(w[i][j] + " ");

}

System.out.println();

}

Условие на e-olymp.com
Решение на e-olymp.com
Код на ideone.com