HDU2544-dijstla-填坑

知识浅谈

发布于 2022-06-22 16:51:49

20300

代码可运行

文章被收录于专栏：分享学习分享学习

运行总次数：0

代码可运行

解决方案：

我反手一个好家伙，查了很多遍，写的没问题啊，最后才发现min设置最大值的时候，设置的Integer.MAX_VALUE,设置这个就是错，所以就看了以前的设置的是0x3f3f3f3f

原因分析

Integer.MAX_VALUE = 0x7fffffff 而之前ac的设置最大值 0x3f3f3f3f ，明显是Integer.MAX_VALUE这个大，按说应该是对的，仔细看了代码才知道，中间用到了dis[j]>dis[k]+rec[k][j]，dis[k]+rec[k][j]这个如果有一个是Integer.MAX_VALUE，相加就超过了Integer.MAX_VALUE，中间寄存器也就存不下会错了

正确Java代码如下：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int n,m,a,b,c;
        Scanner sc = new Scanner(System.in);
        int [][]rec;
        while(true) {
            n = sc.nextInt();
            m = sc.nextInt();
            if (n == 0 && m == 0) break;
            rec = new int[n][n];
            for (int i = 0; i < n; i++) {
                rec[i][i]=0;
                for (int j = i + 1; j < n; j++)
                    rec[i][j] = rec[j][i] = 0x3f3f3f3f;
            }
            for (int i = 0; i < m; i++) {
                a = sc.nextInt();
                b = sc.nextInt();
                c = sc.nextInt();
                if(c<rec[a-1][b-1]) rec[a-1][b-1]=rec[b-1][a-1]=c;
            }
            System.out.println(dij(rec,n));
        }
    }
    public static int dij(int[][]rec,int N){
        boolean[] vis = new boolean[N];
        int[]dis = new int[N];
        for (int i = 0; i <N; i++) {
            vis[i]=false;
            dis[i]=rec[0][i];
        }
        vis[0]=true;dis[0]=0;
        int min1,k;
        for (int i = 1; i < N; i++) {
            min1 = 0x3f3f3f3f;
            k=-1;
            for (int j = 0; j <N ; j++) {
                if(!vis[j]&&min1>dis[j]){
                    min1 = dis[j];
                    k=j;
                }
            }
            if(k==-1) break;
            vis[k]=true;
            for(int j=0;j<N;j++){
                if(!vis[j]&&dis[j]>dis[k]+rec[k][j]) dis[j]=dis[k]+rec[k][j];
            }
        }
        return dis[N-1];
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-06-21，如有侵权请联系 cloudcommunity@tencent.com 删除

java