spfa复盘
作者:
火球大的脸盆
,
2022-08-12 17:54:03
,
所有人可见
,
阅读 207
import java.io.*;
import java.util.*;
public class Main {
static final int N = 100010, INF = 0x3f3f3f3f;
static int n, m, idx;
static int x, y, z;
static int[] ne = new int[N], e = new int[N], h = new int[N], w = new int[N], d = new int[N];
static boolean[] st = new boolean[N];
static Queue<Integer> q = new LinkedList<>();
static void add(int a, int b, int c) {
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
static int spfa() {
Arrays.fill(d, INF);
d[1] = 0;
q.offer(1);
st[1] = true;
while(!q.isEmpty()) {
int x = q.poll();
st[x] = false;
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] > d[x] + w[i]) {
d[j] = d[x] + w[i];
if (!st[j]) {
q.offer(j);
st[j] = true;
}
}
}
}
return d[n];
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] first_line = br.readLine().split(" ");
n = Integer.parseInt(first_line[0]);
m = Integer.parseInt(first_line[1]);
Arrays.fill(h, -1);
while (m-- != 0) {
String[] second_line = br.readLine().split(" ");
x = Integer.parseInt(second_line[0]);
y = Integer.parseInt(second_line[1]);
z = Integer.parseInt(second_line[2]);
add(x, y, z);
}
int ans = spfa();
if (ans > INF / 2) {
bw.write("impossible\n");
bw.flush();
}
else {
bw.write(ans + "\n");
bw.flush();
}
}
}