MY CODE:
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scn = new Scanner(System.in);
int t = scn.nextInt();
for (int i = 0; i < t; i++) {
graph g = new graph();
int nodes = scn.nextInt();
int edges = scn.nextInt();
for (int i1 = 1; i1 <= nodes; i1++) {
String s = "";
s += i1;
g.addVertex(s);
s = "";
}
for (int j = 0; j < edges; j++) {
String v1 = scn.next();
String v2 = scn.next();
int cost = scn.nextInt();
g.addEdges(v1, v2, cost);
}
String src = scn.next();
HashMap<String, Integer> ans = g.Dijkstra(src);
for (String vtx : g.vtcs.keySet()) {
if (vtx.equals(src)) {
continue;
}
System.out.print(ans.get(vtx) + " ");
}
}
}
}
class graph {
public class HeapGeneric<T extends Comparable> {
ArrayList<T> data = new ArrayList<>();
HashMap<T, Integer> map = new HashMap<>();
public void add(T item) {
data.add(item);
map.put(item, this.data.size() - 1);
upheapify(data.size() - 1);
}
private void upheapify(int ci) {
int pi = (ci - 1) / 2;
if (isLarger(data.get(ci), data.get(pi)) > 0) {
swap(pi, ci);
upheapify(pi);
}
}
private void swap(int i, int j) {
T ith = data.get(i);
T jth = data.get(j);
data.set(i, jth);
data.set(j, ith);
map.put(ith, j);
map.put(jth, i);
}
public void display() {
System.out.println(data);
}
public int size() {
return this.data.size();
}
public boolean isEmpty() {
return this.size() == 0;
}
public T remove() {
swap(0, this.data.size() - 1);
T rv = this.data.remove(this.data.size() - 1);
downheapify(0);
map.remove(rv);
return rv;
}
private void downheapify(int pi) {
int lci = 2 * pi + 1;
int rci = 2 * pi + 2;
int mini = pi;
if (lci < this.data.size() && isLarger(data.get(lci), data.get(mini)) > 0) {
mini = lci;
}
if (rci < this.data.size() && isLarger(data.get(rci), data.get(mini)) > 0) {
mini = rci;
}
if (mini != pi) {
swap(mini, pi);
downheapify(mini);
}
}
public T get() {
return this.data.get(0);
}
// if t is having higher priority then return +ve value
public int isLarger(T t, T o) {
return t.compareTo(o);
}
public void updatePriority(T pair) {
int index = map.get(pair);
upheapify(index);
}
}
private class vertex {
HashMap<String, Integer> nbrs = new HashMap<>();
}
HashMap<String, vertex> vtcs;
public graph() {
vtcs = new HashMap<>();
}
public void addVertex(String vname) {
if (vtcs.containsKey(vname)) {
return;
}
vertex vtx = new vertex();
vtcs.put(vname, vtx);
}
public void addEdges(String v1, String v2, int cost) {
vertex vtx1 = vtcs.get(v1);
vertex vtx2 = vtcs.get(v2);
if (vtx1 == null || vtx2 == null || vtx1.nbrs.containsKey(v2)) {
return;
}
vtx1.nbrs.put(v2, cost);
vtx2.nbrs.put(v1, cost);
}
private class DijkstraPair implements Comparable<DijkstraPair> {
String vname;
String psf;
int cost;
@Override
public int compareTo(DijkstraPair o) {
return o.cost - this.cost;
}
}
public HashMap<String, Integer> Dijkstra(String src) {
HashMap<String, Integer> ans = new HashMap<>();
HashMap<String, DijkstraPair> map = new HashMap<>();
HeapGeneric<DijkstraPair> heap = new HeapGeneric<>();
// make a pair and put in heap and map
for (String key : vtcs.keySet()) {
DijkstraPair np = new DijkstraPair();
np.vname = key;
np.psf = "";
np.cost = Integer.MAX_VALUE;
if (key.equals(src)) {
np.cost = 0;
np.psf = key;
}
heap.add(np);
map.put(key, np);
}
// till the heap is not empty keep on removing the pairs
while (!heap.isEmpty()) {
// remove a pair
DijkstraPair rp = heap.remove();
map.remove(rp.vname);
// add to mst
ans.put(rp.vname, rp.cost);
// nbrs
for (String nbr : vtcs.get(rp.vname).nbrs.keySet()) {
// work for nbrs which are in heap
if (map.containsKey(nbr)) {
// get the oc and nc
int oc = map.get(nbr).cost;
int nc = rp.cost + vtcs.get(rp.vname).nbrs.get(nbr);
// update the pair only when nc < oc
if (nc < oc) {
DijkstraPair gp = map.get(nbr);
gp.psf = rp.psf + nbr;
gp.cost = nc;
heap.updatePriority(gp);
}
}
}
}
return ans;
}
}