TreeMap<String, Integer> nameToNum = new TreeMap<String, Integer>();
if(!nameToNum.containsKey(name)){
nameToNum.put(name, nameToNum.size());
}
// copy and paste this to your text editor for better reading experience
// credit: ch2_06_priority_queue.java from CP3 book
import java.util.*;
class pair < X, Y > { // utilizing Java "Generics"
X _first;
Y _second;
public pair(X f, Y s) { _first = f; _second = s; }
X first() { return _first; }
Y second() { return _second; }
void setFirst(X f) { _first = f; }
void setSecond(Y s) { _second = s; }
}
class ch2_06_priority_queue {
public static void main(String[] args) {
// introducing 'pair'
// take note of the use of comparator
PriorityQueue < pair < Integer, String > > pq = new PriorityQueue < pair < Integer, String > >(1,
new Comparator< pair < Integer, String > >() { // overriding the compare method
public int compare(pair < Integer, String > i, pair < Integer, String > j) {
return j.first() - i.first(); // currently max heap, reverse these two to try produce min-heap
}
}
);
// suppose we enter these 7 money-name pairs below
/*
100 john
10 billy
20 andy
100 steven
70 felix
2000 grace
70 martin
*/
pq.offer(new pair < Integer, String > (100, "john")); // inserting a pair in O(log n)
pq.offer(new pair < Integer, String > (10, "billy"));
pq.offer(new pair < Integer, String > (20, "andy"));
pq.offer(new pair < Integer, String > (100, "steven"));
pq.offer(new pair < Integer, String > (70, "felix"));
pq.offer(new pair < Integer, String > (2000, "grace"));
pq.offer(new pair < Integer, String > (70, "martin"));
// this is how we use Java PriorityQueue
// priority queue will arrange items in 'heap' based
// on the first key in pair, which is money (integer), largest first
// if first keys tied, use second key, which is name, largest first
// the internal content of pq heap MAY be something like this:
// re-read (max) heap concept if you do not understand this diagram
// the primary keys are money (integer), secondary keys are names (string)!
// (2000,grace)
// (100,steven) (70,martin)
// (100,john) (10,billy) (20,andy) (70,felix)
// let's print out the top 3 person with most money
pair<Integer, String> result = pq.poll(); // O(1) to access the top / max element + O(log n) removal of the top and repair the structure
System.out.println(result.second() + " has " + result.first() + " $");
result = pq.poll();
System.out.println(result.second() + " has " + result.first() + " $");
result = pq.poll();
System.out.println(result.second() + " has " + result.first() + " $");
}
}
Connect two vertices (L1 and L2) with an edge if L2 = (L1 + Ri) for some button i
if dist[u] is INF, print “Permanently Locked”
O(V+E) BFS, as the graph is unweighted
0 |
3 |
1 |
2 |
9 |
7 |
3 |
4 |
9 |
9 |
1 |
7 |
5 |
5 |
3 |
2 |
3 |
4 |
2 |
5 |
sssp from top-left cell to bottom-right cell + maze[0][0]
The O(VE) Bellman Ford’s is still too slow
0 |
3 |
1 |
2 |
9 |
7 |
3 |
4 |
9 |
9 |
1 |
7 |
5 |
5 |
3 |
2 |
3 |
4 |
2 |
5 |
class IntegerScanner { // only work for all integer input
BufferedInputStream bis;
IntegerScanner(InputStream is) {
bis = new BufferedInputStream(is, 1000000);
}
public int nextInt() {
int result = 0;
try {
int cur = bis.read(); // use read instead of readline
if (cur == -1)
return -1;
while (cur < 48 || cur > 57)
cur = bis.read();
while (cur >= 48 && cur <= 57) { // ASCII values of 0 to 9
result = result * 10 + (cur - 48);
cur = bis.read();
}
return result;
}
catch(IOException ioe) {
return -1;
} } }
counter = 0
for each query p(s,t);
dist[s] = 0; // s is the source vertex
loop V-1 times
change = false;
for each edge (u,v) in L
increase counter by 1;
if dist[u] + weight(u,v) < dist[v]
dist[v] = dist[u] + weight(u,v);
change = true;
if change is false // this is the ’optimized’ Bellman Ford
break from the outermost loop;
output dist[t];
How to make it run in O(VE)?
counter = 0;
for each query p(s,t)
dist[s] = 0; pq.push(pair(0, s)); // pq is a priority queue
while pq is not empty
increase counter by 1;
(d, u) = the top element of pq and then remove it from pq;
if (d == dist[u]) // that important check
for each edge (u,v) in L
if (dist[u] + weight(u,v)) < dist[v]
dist[v] = dist[u] + weight(u,v);
insert pair (dist[v], v) into the pq; // lazy
output dist[t];
How to make this run extremely slowly?
Image courtesy of Francisco Criado, one of Steven's CP book reader from Spain
PriorityQueue<IntegerPair> pq = new PriorityQueue<IntegerPair>();
pq.offer(new IntegerPair(0, s));
while (!pq.isEmpty()) {
IntegerPair top = pq.poll();
int d = top.first(), u = top.second();
if (u == t) break; // to speed up a bit,
// what if 0 is very close to 1 but the graph is very gigantic?
if (d > dist.get(u)) continue; // some of you don’t do this
// what if there are so many inferior information in the PQ?
for (int j = 0; j < AdjList.get(u).size(); j++) {
IntegerPair p = AdjList.get(u).get(j);
int v = p.first(), weight_u_v = p.second();
if (dist.get(u) + weight_u_v < dist.get(v)) {
dist.set(v, dist.get(u) + weight_u_v);
pq.offer(new IntegerPair(dist.get(v), v));
} } }