-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdijkstra.java
More file actions
87 lines (74 loc) · 2.47 KB
/
Copy pathdijkstra.java
File metadata and controls
87 lines (74 loc) · 2.47 KB
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
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.*;
public class dijkstra {
static final int inf = (int) 1e7;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
List<List<Pair>> graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
int[] dist = new int[n + 1];
Arrays.fill(dist, inf);
for (int i = 0; i < m; i++) {
int u = input.nextInt();
int v = input.nextInt();
int w = input.nextInt();
graph.get(u).add(new Pair(v, w));
graph.get(v).add(new Pair(u, w));
}
int source = input.nextInt();
input.close();
dist[source] = 0;
TreeSet<Pair> set = new TreeSet<>();
for (int i = 1; i <= n; i++) {
if (dist[i] < inf)
System.out.print(dist[i] + "\t");
else
System.out.print(-1 + "\t");
}
System.out.println();
set.add(new Pair(0, source));
while (!set.isEmpty()) {
Pair x = set.pollFirst();
int vertex = x.second;
for (Pair i : graph.get(vertex)) {
if (dist[i.first] > dist[vertex] + i.second) {
set.remove(new Pair(dist[i.first], i.first));
dist[i.first] = dist[vertex] + i.second;
set.add(new Pair(dist[i.first], i.first));
}
}
for (int i = 1; i <= n; i++) {
if (dist[i] < inf)
System.out.print(dist[i] + "\t");
else
System.out.print(-1 + "\t");
}
System.out.println();
}
System.out.print("final output: \t");
for (int i = 1; i <= n; i++) {
if (dist[i] < inf)
System.out.print(dist[i] + "\t");
else
System.out.print(-1 + "\t");
}
}
static class Pair implements Comparable<Pair> {
int first;
int second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
@Override
public int compareTo(Pair other) {
if (this.first == other.first) {
return Integer.compare(this.second, other.second);
}
return Integer.compare(this.first, other.first);
}
}
}