AcWing 849. Dijkstra求最短路 I_Java实现含详细解释
原题链接
简单
作者:
FayunYm
,
2021-01-04 20:47:46
,
所有人可见
,
阅读 395
import java.io.*;
import java.util.Arrays;
public class Main {
static int n, m; //结点数,边数
static int[][] g; //邻接矩阵适合表示稠密图
static int[] dist;
static boolean[] status = new boolean[510]; //是否已确定最短路,最好直接赋值,这样默认是false
static final int DIST = 0x3f3f3f3f; //>10^9,大于所有距离之和,可用来表示正无穷
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = reader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
g = new int[n+1][n+1];
dist = new int[n+1];
for(int i = 1; i<= n; i++) {
Arrays.fill(g[i], 1,n+1,DIST);
}
Arrays.fill(dist, 1,n+1,DIST);
while (m-- != 0) {
s = reader.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
int c = Integer.parseInt(s[2]);
g[a][b] = Math.min(g[a][b],c); //应为有重边和自环,所以只保留最短
}
int t = dijkstra();
log.write(t + "");
log.flush();
log.close();
reader.close();
}
private static int dijkstra() {
dist[1] = 0;
for(int i = 0; i < n; i++) { //循环n遍,每次确定一个点的最短路
int t = -1;
for(int j = 1; j <=n; j++) //遍历下所有点,寻找路径最短的点
if(!status[j] && (t == -1 || dist[t] > dist[j])) //找到路径最短的点
t = j;
if(t == n) break; //结点n已经确定最短路,结束程序
status[t] = true; //将这个点加入已确定最短路的点的集合中
for(int j = 1; j <= n; j++) { //更新一下距离
dist[j] = Math.min(dist[j],dist[t] + g[t][j]);
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
}