daily pastebin goal
63%
SHARE
TWEET

CanadianAirlines

a guest Apr 19th, 2018 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.io.PrintWriter;
  4. import java.util.*;
  5.  
  6. public class CanadianAirlines {
  7.     private static ArrayList<Integer>[] graph;
  8.     private static boolean[] used;
  9.     private static int lengthFirstPath = 0;
  10.     private static int answer = -1;
  11.  
  12.     public static void main(String[] args) throws FileNotFoundException {
  13.         Scanner in = new Scanner(new File("in.txt"));
  14.         PrintWriter out = new PrintWriter(new File("out.txt"));
  15.         int n = in.nextInt();
  16.         int m = in.nextInt();
  17.         graph = new ArrayList[n];
  18.         used = new boolean[n];
  19.         Arrays.fill(used, false);
  20.         HashMap<String, Integer> name = new HashMap<>();
  21.         for (int i = 0; i < n; i++) {
  22.             name.put(in.next(), i);
  23.             graph[i] = new ArrayList<>();
  24.         }
  25.         for (int i = 0; i < m; i++) {
  26.             int x = name.get(in.next());
  27.             int y = name.get(in.next());
  28.             if (x < y) {
  29.                 graph[x].add(y);
  30.             } else {
  31.                 graph[y].add(x);
  32.             }
  33.         }
  34.  
  35.         int[][] d = new int[n][n];
  36.         for (int[] di : d) {
  37.             Arrays.fill(di, -1);
  38.         }
  39.         d[0][0] = 1;
  40.         for (Integer u : graph[0]) {
  41.             d[0][u] = 2;
  42.         }
  43.         for (int a = 0; a < n; ++a) {
  44.             for (int b = a + 1; b < n; ++b) {
  45.                 if (d[a][b] == -1) {
  46.                     continue;
  47.                 }
  48.                 for (Integer u : graph[a]) {
  49.                     if (u > b) {
  50.                         d[b][u] = Math.max(d[a][b] + 1, d[b][u]);
  51.                     } else if (u == b && u == n - 1) {
  52.                         d[u][u] = d[a][b] + 1;
  53.                     }
  54.                 }
  55.                 for (Integer u : graph[b]) {
  56.                     d[a][u] = Math.max(d[a][b] + 1, d[a][u]);
  57.                 }
  58.             }
  59.         }
  60.  
  61.         out.println(d[n - 1][n - 1] == -1 ? "No solution" : d[n - 1][n - 1] - 1);
  62.         out.close();
  63.     }
  64. }
RAW Paste Data
Top