AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
半透明の微笑
,
2024-04-23 15:32:29
,
所有人可见
,
阅读 4
import java.io.*;
import java.util.*;
public class Main{
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 n, m;
static int INF = 0x3f3f3f3f;
static void dijkstra(){
dist[1] = 0;
for(int i = 0; i < n; i ++){
int t = -1;
for(int j = 1; j <= n; j ++){
if(!st[j] && (t == -1 || dist[t] > dist[j])){
t = j;
}
}
st[t] = true;
for(int j = 1; j <= n; j ++){
dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
}
if(dist[n] == INF) System.out.println(-1);
else System.out.println(dist[n]);
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
for(int i = 0; i < N; i ++) Arrays.fill(g[i], INF);
for(int i = 0; i < m; i ++){
String[] s2 = br.readLine().split(" ");
int x = Integer.parseInt(s2[0]);
int y = Integer.parseInt(s2[1]);
int z = Integer.parseInt(s2[2]);
g[x][y] = Math.min(g[x][y], z);
}
Arrays.fill(dist, INF);
dijkstra();
}
}