去哪儿笔试第一题第三题

import java.util.*;

public class Main {

    private static String target = "";
    private static Map<String, List<String>> map = new HashMap<String, List<String>>();
    private static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String now = scanner.next();
        target = scanner.next();
        for (int i = 0; i < m; i++) {
            String str1 = scanner.next();
            String str2 = scanner.next();
            if (!map.containsKey(str1)) {
                map.put(str1, new ArrayList<String>());
            }
            if (!map.containsKey(str2)) {
                map.put(str2, new ArrayList<String>());
            }
            map.get(str1).add(str2);
            map.get(str2).add(str1);
        }
        scanner.close();
        find("", now, 0);
        if (min == Integer.MAX_VALUE) {
            System.out.println("DISCONNECTED");
        } else {
            System.out.println(min);
        }
    }
    public static void find(String already, String now, int num) {
        if (already.indexOf(now) != -1) {
            return;
        }
        if (map.containsKey(now)) {
            List<String> list = map.get(now);
            if (list.contains(target)) {
                if (num + 1 < min) {
                    min = num + 1;
                }
            } else {
                already += "|" + now;
                num++;
                for (String str : list) {
                    find(already, str, num);
                }
            }
        }
    }
}

import java.util.*;

public class Main {

    private static String[] target;
    private static String line;
    private static int n;
    private static int min = Integer.MAX_VALUE;
    private static List<List<String>> list = new ArrayList<List<String>>();
    private static int[] array;
    public static void main(String[] args) {
        try {
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            list.add(new ArrayList<String>());
            array = new int[n + 1];
            for (int i = 0; i < n; i++) {
                int index = scanner.nextInt();
                array[index] = scanner.nextInt();
                List<String> airline = new ArrayList<String>();
                int m = scanner.nextInt();
                for (int j = 0; j < m; j++) {
                    airline.add(scanner.next());
                }
                list.add(airline);
            }
            int m = scanner.nextInt();
            target = new String[m];
            for (int i = 0; i < m; i++) {
                target[i] = scanner.next();
            }
            scanner.close();
            String nowStr = target[0];
            for (int i = 1; i <= n; i++) {
                if (list.get(i).contains(nowStr)) {
                    find(String.valueOf(i), 1, i, 0, array[i]);
                }
            }
            if (min == Integer.MAX_VALUE) {
                System.out.println("Error");
            } else {
                System.out.println(min);
                System.out.println(line);
            }
        } catch (Exception e) {
            System.out.println("Error");
        }

    }

    private static void find(String already, int targetIndex, int airlineIndex, int nowIndex, int sum) {
        String targetStr = target[targetIndex];
        List<String> airline = list.get(airlineIndex);
        if (airline.contains(targetStr)) {
            if (targetIndex == target.length -1) {
                if (sum < min) {
                    min = sum;
                    line = already;
                }
            } else {
                find(already, targetIndex + 1, airlineIndex, airline.indexOf(targetStr), sum);
            }
        }
        for (int i = nowIndex + 1; i < airline.size(); i++) {
            find(already, targetIndex, airlineIndex, i, sum);
        }
        String nowStr = airline.get(nowIndex);
        for (int i = 1; i <= n; i++) {
            if (already.indexOf(String.valueOf(i)) == -1) {
                if (list.get(i).get(0).contains(nowStr)) {
                    find(already + " " + i, targetIndex++, i, 0, sum + array[i]);
                }
            }
        }
    }
}