Advertisement
vov44k

160

Jan 26th, 2023
561
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.58 KB | None | 0 0
  1. import java.util.LinkedList;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner in = new Scanner(System.in);
  7.         int n = in.nextInt();
  8.         byte[][] graph = new byte[n][n];
  9.  
  10.         for (int i = 0; i < n; i++) {
  11.             for (int j = 0; j < n; j++) {
  12.                 graph[i][j] = in.nextByte();
  13.             }
  14.         }
  15.  
  16.         int start = in.nextInt() - 1;
  17.         int finish = in.nextInt() - 1;
  18.         int[] way = new int[n];
  19.         for (int i = 0; i < n; i++)
  20.             way[i] = -1;
  21.         way[start] = -1;
  22.         boolean[] used = new boolean[n];
  23.         LinkedList<Integer> q = new LinkedList<>();
  24.         q.add(start);
  25.         boolean yes = true;
  26.         while (!q.isEmpty()) {
  27.             int x = q.pollFirst();
  28.             for (int i = 0; i < n; i++) {
  29.                 if (graph[x][i] == 1 && !used[i]) {
  30.                     q.addLast(i);
  31.                     way[i] = x;
  32.                     used[i] = true;
  33.                 }
  34.             }
  35.         }
  36.  
  37.         int f = 0;
  38.         while (finish != start && f < n + 2) {
  39.             q.addFirst(finish);
  40.             if (way[finish] >= 0)
  41.                 finish = way[finish];
  42.             f++;
  43.         }
  44.         if (f == n + 2)
  45.             System.out.println(-1);
  46.         else {
  47.             System.out.println(q.size());
  48.             if (q.size() != 0) {
  49.             System.out.print(start+1);
  50.             while (!q.isEmpty()) {
  51.                 System.out.print(" " + (q.pollFirst() + 1));
  52.             }
  53.             }
  54.         }
  55.     }
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement