hackerrank_code/Dijkstra.java at master · iamdiv/hackerrank_code · GitHub

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
import java.util.*;
class ShortestPah
{

}
public class Dijkstra{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int x ;
int y,min = 9999999,min1 = 99999 ;
int r,next = 0;
int[][] adjecency = new int[n][n];
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if(i == j){
adjecency[i][j] = 0;
}
else{
adjecency[i][j] = -1;
}
}
}
for(int i=0;i<n;i++){
 x = scan.nextInt();
 y =scan.nextInt();
 r =  scan.nextInt();
adjecency[x-1][y-1] = r;
adjecency[y-1][x-1] = r;
}
int s = scan.nextInt();
if((s-1)!=0){

for(int j = 0;j<n;j++){
int temp = adjecency[s-1][j];
adjecency[s-1][j] = adjecency[0][j];
adjecency[0][j] = temp;

}
}
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
System.out.print(adjecency[i][j] + " ");
}
System.out.println(" ");
}
int[] distance = new int[n];
Boolean sptSet[] = new Boolean[n];
for(int i = 0;i<n;i++){
distance[i] = 999999999;
sptSet[i] = false;
}
distance[s-1] = 0;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if(adjecency[next][j] > 0){
if(sptSet[j] == false &&distance[j]<=min){
min = distance[j];
System.out.print(distance[j] + " " + min);
next = j;
}
}
}
System.out.print(next);
sptSet[next] = true;
for(int k = 0;k<n;k++){
if((distance[next] + adjecency[next][k])<distance[k]){
distance[k] = distance[next] + adjecency[next][k];
}
}
}
for (int i = 0; i < n; i++){
            System.out.println(i+" tt "+distance[i]);
}
}
}