AcWing 849. java-Dijkstra求最短路 I
原题链接
简单
作者:
mkuiwu
,
2021-02-04 14:44:48
,
所有人可见
,
阅读 239
import java.lang.*;
import java.io.*;
import java.util.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer stz = new StringTokenizer("");
static String nextLine() throws Exception {// 读取下一行字符串
return br.readLine();
}
static String next() throws Exception {// 读取下一个字符串
while (!stz.hasMoreTokens()) {
stz = new StringTokenizer(br.readLine());
}
return stz.nextToken();
}
static int nI() throws Exception {// 读取下一个int型数值
return Integer.parseInt(next());
}
static double nD() throws Exception {// 读取下一个double型数值
return Double.parseDouble(next());
}
static long nL() throws Exception {// 读取下一个double型数值
return Long.parseLong(next());
}
static void write(String str) throws Exception{
bw.write(str);
}
static String itoS(int i){
return Integer.toString(i);
}
static void wI(int i) throws Exception{
write(Integer.toString(i));
}
static void flush() throws Exception{
bw.flush();
}
public static void main(String[] args) throws Exception{
new Main().run();
}
final int INF = 0x3f3f3f3f;
final int N = 510;
int[][] g = new int[N][N];
int[] dist = new int[N];
int n, m;
boolean[] isVisited = new boolean[N];
public void run() throws Exception{
n = nI();
m = nI();
// 1. 初始化G
for (int i = 0; i <= n; i++) {
Arrays.fill(g[i], INF);
}
for (int i = 0; i < m; i++) {
int a, b, w;
a = nI();
b = nI();
w = nI();
// 防止重复边
g[a][b] = Math.min(g[a][b], w);
}
wI(dijsktra());
write("\n");
flush();
}
int dijsktra(){
// 1. 初始化距离
Arrays.fill(dist, INF);
dist[1] = 0;
// 2.从剩余的n-1个节点找到最小值
for (int i = 0; i < n-1; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!isVisited[j] && ((t == -1) || dist[t] > dist[j] ))
t = j;
}
// 3. 利用t更新距离数组
for (int j = 1; j <= n; j++) {
dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
isVisited[t] = true;
}
if (dist[n] == INF) return -1;
return dist[n];
}
}