今晚笔试第三题,一直数组越界或语法错误

不知道能不能这么做,dfs从起点到终点再到起点,取路径最小值。一直报数组越界或语法错误,10%
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N,M,S,T;
        while (scanner.hasNextInt()) {
            N = scanner.nextInt();
            M = scanner.nextInt();
            S = scanner.nextInt();
            T = scanner.nextInt();
            int[][] road = new int[N + 1][N + 1];
            for (int i = 0; i < M; i++) {
                int U = scanner.nextInt();
                int V = scanner.nextInt();
                int D = scanner.nextInt();
                road[U][V] = D;
            }
            int[] min = new int[2];
            min[0] = Integer.MAX_VALUE;
            int[] goal = new int[1];
            goal[0] = T;
            dfs(0, S, road, S, goal, min);
            System.out.println(min[0] + " ");
        }
    }

    public static void dfs(int cnt, int cur, int[][] road, int S, int []T, int []min) {
        //标识到达终点min[1] = 1;
        if (cur == T[0] && min[1] == 0) {
            T[0] = S;
            min[1] = 1;
        }
        else if (cur == T[0] && min[1] == 1) {
            min[0] = Math.min(min[0], cnt);
            return;
        }
        for (int i = 1;i < road.length;i ++ ) {
            if (road[cur][i] != 0) {
                cnt += road[cur][i];
                dfs(cnt, i, road, S, T, min);
            }
        }
    }

#笔试题目#
全部评论
快递这题不能用二维数组啊,10000*10000会超内存
点赞 回复
分享
发布于 2018-05-23 21:34
emmmmm我第一反映是用dijikstra…
点赞 回复
分享
发布于 2018-05-23 21:31
小红书
校招火热招聘中
官网直投
一般来说dfs复杂度是爆炸的,稍微有过点acm经历的选手,这题dijkstra或者spfa手写10分钟就过了。
点赞 回复
分享
发布于 2018-05-23 23:12

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务