阿里4.13笔试

第一题：选动物老大，n个小动物，编号1-n,代表武力值，值越小，武力值越高，每个小动物都有一票投票权，可以投给自己或者自己崇拜的动物，或者和自己崇拜的动物跟票。只能崇拜武力值比自己厉害的动物。
输入样例：第一行动物个数， 第二行崇拜对象。
4
0 1 1 1
输出
4
1
1
1
这道题笔试的时候我AC了。
我的解题思路：因为动物只会崇拜能力值比自己高的动物，所以从后向前依次统计每个动物受了多少个其他动物的崇拜，所以每个动物的得票数为崇拜对象数+1（自己给自己投）.

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] an = new int[n];
        int[] pow = new int[n + 1];
        for(int i = 0; i < n; i++){
            an[i] = scanner.nextInt();
        }
        for (int i = an.length - 1; i >= 0; i--) {
            if(an[i] == 0){
                continue;
            }
            pow[an[i]] = pow[an[i]] + pow[i + 1] + 1;
        }
        for (int i = 1; i < pow.length; i++) {
            System.out.println(pow[i] + 1);
        }
    }

第二题：n个城市n个人，每个城市一个人，选择一个城市x，所有人去那聚会，聚合结束所有人返回各自城市。
有m条单向路径，保证每个人可以到达城市x，一个人所消耗时间为往返时间和，每个人选择自己的最短路径，问最长的时间是多少
输入样例：第一行n,m,x,第二行路径
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
输出
10
能不能AC不清楚，测试用例是可以过的
这道题由于时间不足（可能是我太菜），当时写的时候比较慌，出了蛮多问题，14号中午又接到面试，就搁置了。
今天仔细思考了下，还是用暴力方法解决了。我用的是dfs，直接找每个城市到达目的城市的最短路径的最长时间。最后后比较每个城市的时间。

 static int[] mark;//标记数组防止重复访问
    static int step;//记录步数

    public static int minPath(int[][] map, int start, int end, int nowStep){
        int res = 0;
        mark[start] = 1;
        int tmp = Integer.MAX_VALUE;
        for (int i = 1; i < map[start].length; i++) {
            if(map[start][i] == 0 || mark[i] != 0){
                continue;
            }
            if(i == end){
                res = map[start][i];
                break;
            }else{
                step++;
                int tmpRes = minPath(map, i, end, nowStep+1);
                if(tmp > step){
                    res = tmpRes;
                    tmp = step;
                    step = nowStep;
                }
                else if(tmp == step){
                    res = Math.max(tmpRes, res);
                }
            }
        }
        mark[start] = 0;
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int[][] map = new int[n+1][n+1];
        mark = new int[n+1];
        int[] path = new int[n+1];
        for(int i = 1; i <=m; i++){
            int x = scanner.nextInt();
            int y =  scanner.nextInt();
            map[x][y] = scanner.nextInt();
        }
        for (int i = 1; i < path.length; i++) {
            if(i == k){
                continue;
            }
            step = 0;
            path[i] = minPath(map, i, k, 0) + minPath(map, k, i, 0);
        }
        int max = 0;
        for (int i : path) {
            max = Math.max(max, i);
        }
        System.out.println(max);
    }