-
Notifications
You must be signed in to change notification settings - Fork 9
/
Dijkstra.java
56 lines (49 loc) · 1019 Bytes
/
Dijkstra.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
int n,m;
int[][][] g;
int[] from,to,wt;
long[]cost ;
void solve() throws Exception {
n= ni();m=ni();
from = new int[m];
to = new int[m];
wt = new int[m];
for(int i=0;i<m;++i){
from[i]=ni(); to[i]=ni(); wt[i]=ni();
}
g = nwg(n,m,from,to,true);
dijsktra();
/*input Graph from wikipedia page of Dijsktra's Algorithm
6 9
1 2 7
1 3 9
1 6 14
2 3 10
3 6 2
2 4 15
3 4 11
6 5 9
5 4 6
Out : [0, 0, 7, 9, 20, 20, 11]
*/
pn(Arrays.toString(cost));
}
void dijsktra(){
cost=new long[n+1];
cost[1]=0;
boolean vis[]=new boolean[n+1];
PriorityQueue<pair> pq=new PriorityQueue<>();
pq.add(new pair(0,1));
while(!pq.isEmpty()){
// dbg(pq);
pair p=pq.poll();
int vertex = (int)p.y;
long weight= p.x ;
if(vis[vertex]) continue;
vis[vertex]=true;
cost[vertex]=p.x;
for(int[] q :g[vertex]){
if(vis[q[0]]) continue;
pq.add(new pair(wt[q[1]]+weight,q[0]));
}
}
}