-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
815.java
102 lines (92 loc) · 3.32 KB
/
815.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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
__________________________________________________________________________________________________
sample 5 ms submission
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
int maxStop = 0;
for (int[] route : routes) {
for (int stop : route) {
maxStop = Math.max(stop, maxStop);
}
}
++maxStop;
int[] counts = new int[maxStop];
Arrays.fill(counts, maxStop);
counts[S] = 0;
boolean changed = true;
for (int i = 0; i < routes.length && changed; ++i) {
changed = false;
for (int[] route : routes) {
int min = maxStop - 1;
for (int stop : route) {
min = Math.min(min, counts[stop]);
}
++min;
for (int stop : route) {
if (counts[stop] > min) {
counts[stop] = min;
changed = true;
}
}
}
}
return counts[T] == maxStop ? -1 : counts[T];
}
}
__________________________________________________________________________________________________
sample 52700 kb submission
import java.awt.Point;
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S==T) return 0;
int N = routes.length;
List<List<Integer>> graph = new ArrayList();
for (int i = 0; i < N; ++i) {
Arrays.sort(routes[i]);
graph.add(new ArrayList());
}
Set<Integer> seen = new HashSet();
Set<Integer> targets = new HashSet();
Queue<Point> queue = new ArrayDeque();
// Build the graph. Two buses are connected if
// they share at least one bus stop.
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j)
if (intersect(routes[i], routes[j])) {
graph.get(i).add(j);
graph.get(j).add(i);
}
// Initialize seen, queue, targets.
// seen represents whether a node has ever been enqueued to queue.
// queue handles our breadth first search.
// targets is the set of goal states we have.
for (int i = 0; i < N; ++i) {
if (Arrays.binarySearch(routes[i], S) >= 0) {
seen.add(i);
queue.offer(new Point(i, 0));
}
if (Arrays.binarySearch(routes[i], T) >= 0)
targets.add(i);
}
while (!queue.isEmpty()) {
Point info = queue.poll();
int node = info.x, depth = info.y;
if (targets.contains(node)) return depth+1;
for (Integer nei: graph.get(node)) {
if (!seen.contains(nei)) {
seen.add(nei);
queue.offer(new Point(nei, depth+1));
}
}
}
return -1;
}
public boolean intersect(int[] A, int[] B) {
int i = 0, j = 0;
while (i < A.length && j < B.length) {
if (A[i] == B[j]) return true;
if (A[i] < B[j]) i++; else j++;
}
return false;
}
}
__________________________________________________________________________________________________