import java.util.ArrayList;
import java.util.Collections;

public class HW3_2 {
    /**
     * Определяет путь между заданными двумя вершинами такой,
     * что минимальный вес на ребрах этого пути максимален.
     * <p>
     * Реализован алгоритм Форда-Беллмана с динамикой,
     * сложность которого O(V*E).
     *
     * @param from    Начальная вершина
     * @param to      Конечная вершина
     * @param matrix Матрица смежности, если ребро есть, то в ячейке (i, j) лежит вес ребра из i в j, иначе -1.
     * @return Список вершин, составляющих такой путь (от начальной к конечной),
     * или null, если такого пути нет.
     */
    public static ArrayList<Integer> FB(int from, int to, int[][] matrix) {
        int n = matrix.length;
        int[] d = new int[n];
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = -1;
            p[i] = -1;
        }
        d[from] = Integer.MAX_VALUE;

        for (int v = 0; v < n; v++) {
            for (int u = 0; u < n; u++) {
                if (matrix[v][u] != -1 && d[u] < Math.min(d[v], matrix[v][u])) {
                    d[u] = Math.min(d[v], matrix[v][u]);
                    p[u] = v;
                }
            }
        }

        //Путь не найден
        if (d[to] == -1) {
            return null;
        }

        ArrayList<Integer> path = new ArrayList<>();
        path.add(to);
        int cur = p[to];

        while (cur != -1) {
            path.add(cur);
            cur = p[cur];
        }

        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        int n = 7;
        int[][] matrix = new int[n][n];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                matrix[i][j] = -1;
            }
        }

        matrix[0][1] = 5;
        matrix[0][5] = 2;
        matrix[1][2] = 1;
        matrix[1][3] = 3;
        matrix[2][4] = 6;
        matrix[3][4] = 3;
        matrix[5][6] = 3;
        matrix[6][4] = 2;

        ArrayList<Integer> FB = FB(0, 4, matrix);

        System.out.println(FB == null ? "No path" : FB.toString());
    }
}