-
Notifications
You must be signed in to change notification settings - Fork 15
/
shortestpath1.java
74 lines (68 loc) · 2.29 KB
/
shortestpath1.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.io.*;
import java.util.*;
public class shortestpath1 {
private static int[] dist;
private static ArrayList<Edge>[] nodes;
@SuppressWarnings("unchecked")
public static void main(String[] args) throws Exception {
BufferedReader sc = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
BufferedWriter dc = new BufferedWriter(new OutputStreamWriter(System.out), 1 << 16);
for (;;) {
String line = sc.readLine();
if (line.equals("0 0 0 0"))
break;
String[] arr = line.split(" ");
int N, M, Q, S;
N = Integer.parseInt(arr[0]);
M = Integer.parseInt(arr[1]);
Q = Integer.parseInt(arr[2]);
S = Integer.parseInt(arr[3]);
dist = new int[N];
nodes = new ArrayList[N];
for (int x = 0; x < N; x++)
nodes[x] = new ArrayList<Edge>();
while (M-- > 0) {
arr = sc.readLine().split(" ");
int u, v, w;
u = Integer.parseInt(arr[0]);
v = Integer.parseInt(arr[1]);
w = Integer.parseInt(arr[2]);
nodes[u].add(new Edge(v, w));
}
dijkstra(S);
while (Q-- > 0) {
int a = Integer.parseInt(sc.readLine());
dc.write(dist[a] == Integer.MAX_VALUE ? "Impossible\n" : dist[a] + "\n");
}
dc.write('\n');
}
dc.close();
sc.close();
}
private static void dijkstra(int source) {
PriorityQueue<Edge> q = new PriorityQueue<Edge>();
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
q.add(new Edge(source, 0));
while (!q.isEmpty()) {
Edge cur = q.poll();
if (cur.weight > dist[cur.to])
continue;
for (Edge nxt : nodes[cur.to]) {
int d = cur.weight + nxt.weight;
if (d < dist[nxt.to])
q.add(new Edge(nxt.to, dist[nxt.to] = d));
}
}
}
}
class Edge implements Comparable<Edge> {
public int weight, to;
public Edge(int a, int b) {
to = a;
weight = b;
}
public int compareTo(Edge a) {
return weight - a.weight;
}
}