首页 > 牛客周周练:MIKU酱。求教小伙伴
头像
毛唔
编辑于 2020-08-04 23:32
+ 关注

牛客周周练:MIKU酱。求教小伙伴



题目链接如上,把题目copy过来了。最下是我自己的代码,也看过别人AC的代码,但还是不明白为什么自己的代码只能过10%,示例输入能通过。求教小伙伴是哪里的问题,或者给一个通过不了的示例也好…求助求助,谢谢🙏
--------------------------------------
得到小伙伴的启示后又改了些地方,现在通过40%了😢,还是很想知道是哪里的问题


MIKU酱是个玩游戏氪金的人,游戏公司给她制定了新的规则,如果想从关卡i到关卡j,你需要交一些钱就可以了,但同时,MIKU酱的爸爸zjw很爱她,所以她可以每过一关就向她爸要一次钱,但她爸每次给他的钱是固定的,MIKU酱是个不会节省的女孩,哪怕每次多出来的钱,她也会拿去买肥宅快乐水,所以每次要的钱一定花完,因为MIKU酱不想挨骂,所以希望每次他爸给她的钱最少。
tips(到达第n关即通过,每到达一关一定能通过这关)

输入描述: 多组输入,每个样例第一行输入两个整数n,m(2<=n<=200,1<=m<=1000)表示关卡和规则的数量,接下来m行规则,每行输入x,y,w(w<=1000),表示从关卡x到y需要缴纳w的费用,保证题目有解,不会出现x=y的情况

输出一行,代表最少的钱

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            int n = in.nextInt();
            int m = in.nextInt();
            int[] dp = new int[n + 1];
            int[][] map = new int[n + 1][n + 1];
            for (int i = 2; i <= n; i++) {
                dp[i] = Integer.MAX_VALUE;
            }

            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= n; j++) {
                    map[i][j] = Integer.MAX_VALUE;
                }
            }

            for (int i = 0; i < m; i++) {
                int x = in.nextInt();
                int y = in.nextInt();
                int w = in.nextInt();
                int sou = Math.min(x, y);
                int des = Math.max(x, y);
                map[sou][des] = Math.min(map[sou][des],w);
            }

            for (int i = 1; i <= n; i++) {
                for (int j = i + 1; j <= n; j++) {
                    if (map[i][j] != Integer.MAX_VALUE) {
                        dp[j] = Math.min(Math.max(dp[i], map[i][j]), dp[j]);
                    }
                }
            }

            System.out.println(dp[n]);
        }

    }
}




全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐