AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
microboat
,
2024-03-18 21:30:00
,
所有人可见
,
阅读 5
// m >> n,稠密图,使用邻接矩阵
import java.io.*;
public class Main {
static int n,m;
static int N = 510;
static int[][] g = new int[N][N];
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
static int maxValue = Integer.MAX_VALUE / 2;
public static int dijkstra() {
// 1、初始化距离
for (int i = 0; i < N; i++) {
dist[i] = maxValue;
}
dist[1] = 0;
// 2、遍历所有点
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
// j 还没被使用(距离还没有确定)、且 t 的距离 比 j 的距离大(找到一个最小距离的 j),取到 t 的值
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
// t 放入已确定的集合中
st[t] = true;
// 用 t 更新其他点到起点的距离
for (int j = 1; j <= n; j++) {
dist[j] = dist[j] < dist[t] + g[t][j] ? dist[j] : dist[t] + g[t][j];
}
}
if (dist[n] == maxValue) {
return -1;
}
return dist[n];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line1 = br.readLine().split(" ");
n = Integer.parseInt(line1[0]);
m = Integer.parseInt(line1[1]);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) {
g[i][j] = 0;
} else {
g[i][j] = maxValue;
}
}
}
while (m-- > 0) {
String[] line2 = br.readLine().split(" ");
int x = Integer.parseInt(line2[0]);
int y = Integer.parseInt(line2[1]);
int z = Integer.parseInt(line2[2]);
g[x][y] = g[x][y] < z ? g[x][y] : z;
}
int t = dijkstra();
System.out.print(t);
}
}