AcWing 850. Dijkstra求最短路 II(小根堆)
原题链接
简单
作者:
半透明の微笑
,
2024-04-23 16:08:04
,
所有人可见
,
阅读 4
import java.io.*;
import java.util.*;
public class Main{
static int N = 200010;
static int[] h = new int[N];
static int[] w = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx;
static int[] dist = new int[N];
static int INF = 0x3f3f3f3f;
static boolean[] st = new boolean[N];
static int n, m;
static PriorityQueue<PII> q = new PriorityQueue<>(new Comparator<PII>(){
@Override
public int compare(PII a, PII b){
return a.d - b.d;
}
});
static void dijkstra(){
dist[1] = 0;
q.add(new PII(0, 1));
while(!q.isEmpty()){
PII t = q.poll();
int d = t.d;
int id = t.id;
if(st[id]) continue;
for(int i = h[id]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > d + w[i]){
dist[j] = d + w[i];
q.add(new PII(dist[j], j));
}
}
st[id] = true;
}
if(dist[n] == INF) System.out.println(-1);
else System.out.println(dist[n]);
}
static void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
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]);
Arrays.fill(h, -1);
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]);
add(x, y, z);
}
Arrays.fill(dist, INF);
dijkstra();
}
}
class PII{
int d;
int id;
public PII(int d, int id){
this.d = d;
this.id = id;
}
}