AcWing 1507. java邻接表 + 堆优化的Dijkstra
原题链接
中等
作者:
佐助
,
2024-04-19 16:18:24
,
所有人可见
,
阅读 4
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main{
static class Pair{
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static int N = 2000, INF = 0x3f3f3f3f;
static int [] h = new int [N];
static int [] ne = new int [N];
static int [] e = new int [N];
static int [] w = new int [N];
static int [] c = new int [N];
static int n, m, S, D, idx;
static int [] dist = new int [N];
static int [] cost = new int [N];
static PriorityQueue<Pair> q = new PriorityQueue<>((a, b) -> (a.y - b.y));
static int [] pre = new int [N];
static boolean [] st = new boolean [N];
static void add(int a, int b, int weight, int price) {
e[idx] = b;
w[idx] = weight; //边权
c[idx] = price;
ne[idx] = h[a];
h[a] = idx ++;
}
static void dijkstra() {
Arrays.fill(dist, INF);
Arrays.fill(cost, INF);
q.offer(new Pair(S, 0));
dist[S] = 0;
cost[S] = 0;
pre[S] = -1;
while(!q.isEmpty()) {
Pair pair = q.poll();
int u = pair.x;
int distance = pair.y;
if(st[u]) continue;
st[u] = true;
for(int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if(dist[j] > distance + w[i]) {
cost[j] = cost[u] + c[i];
pre[j] = u;
dist[j] = distance + w[i];
q.offer(new Pair(j, dist[j]));
}
else if(dist[j] == distance + w[i]){
if(cost[j] > cost[u] + c[i]) {
cost[j] = cost[u] + c[i];
pre[j] = u;
}
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Arrays.fill(h, -1);
n = sc.nextInt();
m = sc.nextInt();
S = sc.nextInt();
D = sc.nextInt();
while(m -- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int len = sc.nextInt();
int price = sc.nextInt();
add(a, b, len, price);
add(b, a, len, price);
}
dijkstra();
ArrayList<Integer> res = new ArrayList<>();
for(int i = D; i != -1; i = pre[i]) {
res.add(i);
}
Collections.reverse(res);
for(int i = 0; i < res.size(); i ++)
System.out.print(res.get(i) + " ");
System.out.print(dist[D] + " " + cost[D]);
}
}