问题

解决这样一类问题，起点确定的，可以有重边和自环的，各边权都为正数的稠密图的最短路问题

要素

  1. g[][]邻接矩阵，存储图的信息
  2. st[]记录已经确定最短距离的点

  3. dist[] 存储每个点到起点的最短距离

    思路

    dist[]， st[] 分别存储起点到各点的最短距离，各点最短距离是否已经确定

  4. Arrays.fill[dist, INF]; dist[1] = 0

  5. for(i : 1~n)

遍历各个节点，找到
t <- 不在st中的距离起点最近的点

st <- t加入该点到st
遍历t的临边，更新临点到起点的最短距离

时间复杂度：O(N^2)
本质：贪心

模板

849. Dijkstra求最短路 I

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
输入样例：

  1. 3 3
  2. 1 2 2
  3. 2 3 1
  4. 1 3 4

输出样例：

  1. 3

代码：

  1. import java.util.*;
  3. public class Main {
  4.     static final int N = 510;
  5.     static int[][] g = new int[N][N];
  6.     static int[] dist = new int[N];
  7.     static boolean[] st = new boolean[N];
  8.     static int n, m;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  12.         m = sc.nextInt();
  13.         for (int i = 0; i < N; i++) {
  14.             Arrays.fill(g[i], 0x3f3f3f3f);
  15.             g[i][i] = 0;
  16.         }
  17.         for (int i = 0; i < m; i++) {
  18.             int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
  19.             g[a][b] = Math.min(g[a][b], c);
  20.         }
  22.         dijkstra(1, dist);
  23.         if (dist[n] != 0x3f3f3f3f)
  24.             System.out.println(dist[n]);
  25.         else
  26.             System.out.println(-1);
  27.     }
  29.     static void dijkstra(int start, int[] dist) {
  30.         Arrays.fill(dist, 0x3f3f3f3f);
  31.         Arrays.fill(st, false);
  32.         dist[start] = 0;
  34.         for (int i = 1; i < n; i++) {
  35.             int t = -1;
  36.             for (int j = 1; j <= n; j++) {
  37.                 if (!st[j] && (t == -1 || dist[j] < dist[t]))
  38.                     t = j;
  39.             }
  41.             st[t] = true;
  42.             for (int j = 1; j <= n; j++)
  43.                 dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
  44.         }
  45.     }
  46. }