Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## JAVACODE DIJKSTRA

Posted by SmartChen at 2018-10-28 16:42:50 on Problem 3255
``` import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Vector;
public class Main {
static int[] dis;
static int[] dis2;
public static void main(String[] args) throws IOException {
final int INF = Integer.MAX_VALUE/3;
Vector<Vector<edge>> G = new Vector<Vector<edge>>();
PriorityQueue<P> pq = new PriorityQueue<P>(100020, new Comparator<P>() {
@Override
public int compare(P o1, P o2) {
return o1.dis - o2.dis;
}
});
Vector<edge> tv;
dis = new int[N];
dis2 = new int[N];
//init
for (int i = 0; i < N; i++) {
tv = new Vector<edge>();
dis[i] = INF;
dis2[i] = INF;
}
for (int i = 0; i < R; i++) {
edge temp = new edge();
int a = Reader.nextInt() - 1;
int b = Reader.nextInt() - 1;
temp.cost = d;
temp.to = b;
tv = G.get(a);
temp = new edge();
temp.cost = d;
temp.to = a;
tv = G.get(b);
}
//dijkstra
{
dis[0] = 0;
P tp = new P();
while (!pq.isEmpty()) {
tp = pq.poll();
tv = G.get(tp.id);
if (dis2[tp.id] < tp.dis) continue;//pruning
for (int i = 0; i < tv.size(); i++) {
int d2 = tp.dis + tv.get(i).cost;
int to = tv.get(i).to;
if (dis[to] > d2) {
//swap, use swapping to avoid the missing of dis[to], it can be the value of dis2 later.
int temp = dis[to];
dis[to] = d2;
d2 = temp;
}
if (dis2[to] > d2 && d2 != dis[to]) {
dis2[to] = d2;
}
}
}
}
System.out.print(dis2[N - 1]);
}
}
class P {
int dis, id;
public P(int x, int y) {
dis = x;
id = y;
}
public P(){};
}
class edge {
int to, cost;
}
static StringTokenizer tokenizer;
/** call this method to initialize reader for InputStream */
static void init(InputStream input) {
tokenizer = new StringTokenizer("");
}
/** get next word */
static String next() throws IOException {
while ( ! tokenizer.hasMoreTokens() ) {
//TODO add check for eof if necessary
tokenizer = new StringTokenizer(
}
}
static int nextInt() throws IOException {
return Integer.parseInt( next() );
}
}
```

Followed by: