图论：最短路径Dijkstra朴素算法

import java.util.*;

public class Main {
    static Scanner in=new Scanner(System.in);

    public static void main(String[] args) {
        int n,m,start;
        n=in.nextInt();
        m=in.nextInt();
        start=in.nextInt();
        int [][]graph=new int[n+1][n+1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(graph[i],Integer.MAX_VALUE);
        }
        for (int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int w = in.nextInt();
            //如果有重边,需要取最小,如果没有直接读入即可
            graph[u][v] = Math.min(graph[u][v], w);
        }
        int[] minDist=new int[n+1];
        //初始节点为0,其他设为遥不可及
        Arrays.fill(minDist,Integer.MAX_VALUE);
        minDist[start]=0;
        boolean[] visited=new boolean[n+1];

        //遍历所有节点
        for (int i=1;i<=n;i++){
            int cur=start;
            int minVal=Integer.MAX_VALUE;
            //找一个数组中最小的那个值并获取最小值的索引
            for (int j = 1; j <=n ; j++) {
                if (!visited[j]&&minDist[j]<minVal){
                    minVal=minDist[j];
                    cur=j;
                }
            }
            //标记当前节点访问过
            visited[cur]=true;
            //遍历当前节点能直接到达的所有路径,并更新所有未访问节点到原点的距离
            for (int j = 1; j <=n; j++) {
                //三个条件:未访问过,新路径比原路径小,当前位置指向的不是遥不可及的节点(也就是可以直接指向)
                if (!visited[j]&&graph[cur][j]+minDist[cur]<minDist[j]&&graph[cur][j]!=Integer.MAX_VALUE) {
                    minDist[j]=minDist[cur]+graph[cur][j];
                }
            }

        }
        System.out.print(minDist[1]);
        for (int i = 2; i <=n ; i++) {
            System.out.print(" "+minDist[i]);
        }

    }

}

//使用邻接矩阵可能超内存
//迪杰斯特拉算法的权值不能有负数