题目描述

朴素dijkstra 模板打卡

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

JAVA 代码

import java.util.Scanner; 
import java.util.Arrays; 
import java.lang.Math; 
class Main{
    static int N = 510;
    static int[][] g;
    static int[] dist;//每个店到1号点的距离，下标从1开始
    static boolean[] st;//是否已经确定最短路的集合
    static void init(int n,int m){
        g = new int [N][N];
        dist = new int [N];
        st = new boolean [N];
        //所有的边和距离初始化为正无穷
        for(int []gg: g)Arrays.fill(gg,0x3f3f3f3f);
        Arrays.fill(dist,0x3f3f3f3f);
        dist[1]=0;
        //读入边
        while(m-->0){
            int a = sc.nextInt(),b =sc.nextInt(),v =sc.nextInt();
            g[a][b] = Math.min(g[a][b],v);
        }
    }
    static int dijkstra(int n){
        for(int i=0;i<n;i++){
            int t=-1;
            for(int j=1;j<=n;j++)if(!st[j] && (t == -1 || dist[j] < dist[t]))t = j;
            if(t == -1) break;
            st[t] =true;
            //更新t相连的边到1号点最小距离
            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]; 
    }
    static Scanner sc= new Scanner(System.in);
    public static void main(String[]args){
        int n = sc.nextInt(), m = sc.nextInt();
        init(n,m);
        System.out.println(dijkstra(n));
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla