题目描述

朴素Dijkstra求最短路

算法1

$O(n^2)$

java 代码

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[][] g=new int[n+1][n+1];
        for(int i=0;i<=n;i++){
            Arrays.fill(g[i],0x3f3f3f3f);
        }
        int from,to,d;
        for(int i=0;i<m;i++){
            from=sc.nextInt();
            to=sc.nextInt();
            d=sc.nextInt();
            g[from][to]=Math.min(g[from][to],d);
        }

        System.out.println(dij(g,n));
    }

    static int dij(int[][] g,int n){
        boolean[] status=new boolean[n+1];
        int[] dist=new int[n+1];
        Arrays.fill(dist,0x3f3f3f3f);
        dist[1]=0;
        for(int i=0;i<n;i++){
            int t=-1;
            for(int j=1;j<=n;j++){
                if(!status[j] && (t==-1 || dist[t] > dist[j] ))
                    t=j;
            }
            status[t]=true;
            for(int j=1;j<=n;j++){
                dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
            }
        }

        return dist[n]==0x3f3f3f3f?-1:dist[n];
    }

}