给定一个 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。
3 3
1 2 2
2 3 1
1 3 4
3
模板题啦,一定要掌握的
以上这张图是最短路算法问题的解法算法
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int n, m, N = 10010;
static int[] dis = new int[510];
static int[][] g = new int[510][510];
static boolean[] state = new boolean[510]; // 记录节点状态,true表示已确定最短路径
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
m = in.nextInt();
// 初始化邻接矩阵,初始值为 N 表示无穷大
for (int i = 1; i <= n; i++) {
Arrays.fill(g[i], N);
}
// 输入图的边信息,记录最小的边权值
for (int i = 0; i < m; i++) {
int x = in.nextInt();
int y = in.nextInt();
int z = in.nextInt();
g[x][y] = Math.min(g[x][y], z);
}
System.out.println(dijkstra());
}
public static int dijkstra() {
Arrays.fill(dis, N); // 初始化距离数组,初始值为 N 表示无穷大
dis[1] = 0; // 起点到自身距离为0
// 循环进行n次,每次找到一个离起点最近的节点,更新其相邻节点的距离
for (int i = 1; i < n; i++) {
int t = -1; // t 存储当前访问的节点
// 找到未确定最短路径的节点中距离起点最近的节点
for (int j = 1; j <= n; j++) {
if (!state[j] && (t == -1 || dis[t] > dis[j])) {
t = j;
}
}
state[t] = true; // 将该节点标记为已确定最短路径
// 更新相邻节点的距离
for (int j = 1; j <= n; j++) {
dis[j] = Math.min(dis[j], dis[t] + g[t][j]);
}
}
return dis[n] == N ? -1 : dis[n]; // 如果终点距离为无穷大,说明不可达,返回-1,否则返回最短距离
}
}
输入: 从输入中获取节点数 n
、边数 m
以及图的边信息。
初始化: 初始化邻接矩阵 g
和距离数组 dis
,将所有距离初始值设置为无穷大 N
,状态数组 state
用于记录节点的最短路径是否已确定。
构建图: 遍历输入的边信息,记录每条边的最小权值。
Dijkstra 算法: 使用 Dijkstra 算法求解最短路径。
输出结果: 输出终点到起点的最短距离,若不可达则输出 -1