AcWing 850. java-Dijkstra求最短路 II
原题链接
简单
作者:
mkuiwu
,
2021-02-04 15:53:18
,
所有人可见
,
阅读 271
import java.lang.*;
import java.io.*;
import java.util.*;
class Pair{
public int key, val;
Pair(int key, int val){
this.key = key;
this.val = val;
}
}
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 = 150100;
int[] dist = new int[N];
int n, m, idx;
boolean[] isVisited = new boolean[N];
PriorityQueue<Pair> heap = new PriorityQueue<>(((o1, o2) -> o1.key - o2.key));
int[] h = new int[N], e = new int[N], ne = new int[N], ws = new int[N];
void add(int a, int b, int w){
ws[idx] = w;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
public void run() throws Exception{
n = nI(); m = nI();
// 初始化邻接表
for (int i = 0; i <= n; i++) {
h[i] = -1;
}
int a, b, w;
for (int i = 0; i < m; i++) {
a = nI(); b = nI(); w = nI();
add(a, b, w);
}
wI(dijsktra());
write("\n");
flush();
}
int dijsktra(){
// 1. 初始化距离
for (int i = 0; i <= n; i++) {
dist[i] = INF;
}
dist[1] = 0;
// 将第一个节点加入队列
heap.add(new Pair(0, 1));
// 2.从剩余的节点找到最小值
while (!heap.isEmpty()){
Pair t = heap.poll();
// 获得集合中最短距离
int ver = t.val;
// 如果已经背访问过
if (isVisited[ver]) continue;
// 3. 利用当前节点更新距离数组
for (int i = h[ver]; i != -1 ; i = ne[i]) {
// h[i] 指向的每一个j 进行判断, 是的 因为e[j] 才是存储的边的下表
int j = e[i];
if (dist[j] > dist[ver] + ws[i]){
dist[j] = dist[ver] + ws[i];
heap.add(new Pair(dist[j], j));
}
}
}
if (dist[n] == INF) return -1;
return dist[n];
}
}