HackerRank Going to the Office problem solution

In this HackerRank Going to the Office problem solution Ms.Kox enjoys her job, but she does not like to waste extra time traveling to and from her office. After working for many years, she knows the shortest-distance route to her office on a regular day.

Recently, the city began regular maintenance of various roads. Every day a road gets blocked and no one can use it that day, but all other roads can be used. You are Ms. Kox’s new intern and she needs some help. Every day, you need to determine the minimum distance that she has to travel to reach her office.

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static class Edge {
    int v;
    long w;

    public Edge(int v, long w) {
      this.v = v;
      this.w = w;
    }
  }

  static class Node implements Comparable<Node> {
    long d;
    int v;

    public Node(long d, int v) {
      this.d = d;
      this.v = v;
    }

    @Override
    public int compareTo(Node o) {
      if (d == o.d) return 0;
      return d > o.d ? 1 : -1;
    }
  }

  static int[] nxt;
  static Edge[] succ;
  static int[] ptr;
  static int index = 1;

  static void add(int u, int v, long w) {
    nxt[index] = ptr[u];
    ptr[u] = index;
    succ[index++] = new Edge(v, w);

    nxt[index] = ptr[v];
    ptr[v] = index;
    succ[index++] = new Edge(u, w);
  }

  static int time = 0;
  static int[] disc;
  static int[] low;
  static boolean[] vis;
  static long[] dis;
  static int[] parent;

  static class NodeDfs {
    int u;
    int p;
    boolean start = true;

    public NodeDfs(int u, int p) {
      this.u = u;
      this.p = p;
    }
  }

  static class HEdge {
    int u;
    int v;

    public HEdge(int u, int v) {
      if (u > v) {
        int tmp = u;
        u = v;
        v = tmp;
      }
      this.u = u;
      this.v = v;
    }

    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result + u;
      result = prime * result + v;
      return result;
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj) return true;
      if (obj == null) return false;
      if (getClass() != obj.getClass()) return false;
      HEdge other = (HEdge) obj;
      if (u != other.u) return false;
      if (v != other.v) return false;
      return true;
    }
  }

  static Set<HEdge> bridges = new HashSet<>();

  static void bridgeDfs(int s) {
    Deque<NodeDfs> queue = new LinkedList<>();
    queue.add(new NodeDfs(s, -1));
    while (!queue.isEmpty()) {
      NodeDfs node = queue.peekLast();
      if (node.start) {
        if (!vis[node.u]) {
          vis[node.u] = true;
          disc[node.u] = low[node.u] = ++time;

          for (int i = ptr[node.u]; i > 0; i = nxt[i]) {
            parent[succ[i].v] = node.u;
            queue.add(new NodeDfs(succ[i].v, node.u));
          }

          node.start = false;
        } else {
          if (node.u != parent[node.p]) {
            low[node.p] = Math.min(low[node.p], disc[node.u]);
          }
          queue.removeLast();
        }
      } else {
        if (node.p >= 0) {
          low[node.p] = Math.min(low[node.p], low[node.u]);

          if (low[node.u] > disc[node.p]) {
            bridges.add(new HEdge(node.p, node.u));
          }
        }
        queue.removeLast();
      }
    }
  }

  static void dijkstra1(int src) {
    dis[src] = 0;
    PriorityQueue<Node> queue = new PriorityQueue<>();
    queue.add(new Node(0, src));
    while (!queue.isEmpty()) {
      Node x = queue.poll();
      if (vis[x.v]) {
        continue;
      }
      vis[x.v] = true;

      for (int i = ptr[x.v]; i > 0; i = nxt[i]) {
        Edge e = succ[i];

        if (x.d + e.w < dis[e.v]) {
          queue.add(new Node(dis[e.v] = x.d + e.w, e.v));
          parent[e.v] = x.v;
        }
      }
    }
  }

  static long dijkstra2(int src, int des, int uBlocked, int vBlocked) {
    dis[src] = 0;
    PriorityQueue<Node> queue = new PriorityQueue<>();
    queue.add(new Node(0, src));
    while (!queue.isEmpty()) {
      Node node = queue.poll();
      if (vis[node.v]) {
        continue;
      }
      vis[node.v] = true;

      for (int i = ptr[node.v]; i > 0; i = nxt[i]) {
        Edge e = succ[i];
        if ((node.v == uBlocked && e.v == vBlocked) || (node.v == vBlocked && e.v == uBlocked)) {
          continue;
        }
        if (node.d + e.w < dis[e.v]) {
          queue.add(new Node(dis[e.v] = node.d + e.w, e.v));
        }
      }
      if (node.v == des) {
        return dis[des];
      }
    }
    return -1;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    ptr = new int[n];
    parent = new int[n];
    nxt = new int[2 * m + 1];
    succ = new Edge[2 * m + 1];

    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());
      int w = Integer.parseInt(st.nextToken());

      add(u, v, w);
    }

    st = new StringTokenizer(br.readLine());
    int s = Integer.parseInt(st.nextToken());
    int d = Integer.parseInt(st.nextToken());

    vis = new boolean[n];
    disc = new int[n];
    low = new int[n];
    bridgeDfs(s);

    dis = new long[n];
    Arrays.fill(dis, Long.MAX_VALUE / 3);
    Arrays.fill(vis, false);
    dijkstra1(s);

    boolean[] b = new boolean[n];
    b[d] = true;
    b[s] = true;
    int p = d;
    while ((p = parent[p]) != s) {
      b[p] = true;
    }

    st = new StringTokenizer(br.readLine());
    int q = Integer.parseInt(st.nextToken());

    long nope = dis[d];

    for (int i = 0; i < q; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());

      long result = nope;
      if ((parent[u] == v || parent[v] == u) && b[u] && b[v]) {
        if (bridges.contains(new HEdge(u, v))) {
          result = -1;
        } else {
          Arrays.fill(dis, Long.MAX_VALUE / 3);
          Arrays.fill(vis, false);
          result = dijkstra2(s, d, u, v);
        }
      }

      if (result >= 0) {
        bw.write(result + "n");
      } else {
        bw.write("Infinityn");
      }
    }

    bw.newLine();

    br.close();
    bw.close();
  }
}

Problem solution in C++.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
#define LCH(No) (No + 1)
#define RCH(No, l, r) (No + r - l + 2 - ((r ^ l) & 1))
const int MAXN = 200010, MAXM = 200010, MAXQ = 200010, MAXS = 19;
const ll INF = ~0Ull >> 2;
struct edge {
	int a, b, w, pre, next;
	bool Z;
} _E[MAXM + MAXM + MAXN], E[MAXN << 1];
struct query {
	int a, b;ll res;
} SQ[MAXQ];
struct pqnode {
	int No;ll d0;
	bool operator<(pqnode q0) const {
		return d0 > q0.d0;
	}
};
ll T[MAXN << 1];
priority_queue<pqnode, vector<pqnode> > PQ;
int n, nq, n0, _m, m, s, t, Q[MAXN], pr0[MAXN], pr[MAXN], DEP[MAXN], ts[MAXN],
		prs[MAXN][MAXS], l0, r0;
ll dist[MAXN], dist2[MAXN], v0, res[MAXN];
bool vst[MAXN], vst2[MAXN];
void init_d() {
	re(i, n)
		_E[i].pre = _E[i].next = E[i].pre = E[i].next = i;
	m = n;
	if (n & 1)
		_m = n + 1;
	else
		_m = n;
}
void add_edge_(int a, int b, int w) {
	_E[_m].a = a;
	_E[_m].b = b;
	_E[_m].w = w;
	_E[_m].pre = _E[a].pre;
	_E[_m].next = a;
	_E[a].pre = _m;
	_E[_E[_m].pre].next = _m++;
	_E[_m].a = b;
	_E[_m].b = a;
	_E[_m].w = w;
	_E[_m].pre = _E[b].pre;
	_E[_m].next = b;
	_E[b].pre = _m;
	_E[_E[_m].pre].next = _m++;
}
void add_edge(int a, int b, int w) {
	E[m].a = a;
	E[m].b = b;
	E[m].w = w;
	E[m].pre = E[a].pre;
	E[m].next = a;
	E[a].pre = m;
	E[E[m].pre].next = m++;
}
void init() {
	int m0, a0, b0, w0;
	scanf("%d%d", &n, &m0);
	init_d();
	re(i, m0)
	{
		scanf("%d%d%d", &a0, &b0, &w0);
		add_edge_(a0, b0, w0);
	}
	scanf("%d%d%d", &s, &t, &nq);
	re(i, nq)
	{
		scanf("%d%d", &SQ[i].a, &SQ[i].b);
		SQ[i].res = -1;
	}
}
void prepare() {
	re(i, n)
		dist[i] = INF;
	dist[s] = 0;
	pqnode q0;
	q0.No = s;
	q0.d0 = 0;
	PQ.push(q0);
	int x, y;
	ll d0;
	while (!PQ.empty()) {
		x = PQ.top().No;
		PQ.pop();
		if (!vst[x]) {
			vst[x] = 1;
			for (int p = _E[x].next; p != x; p = _E[p].next) {
				y = _E[p].b;
				d0 = dist[x] + _E[p].w;
				if (d0 < dist[y]) {
					q0.d0 = dist[y] = d0;
					q0.No = y;
					PQ.push(q0);
				}
			}
		}
	}
	if (dist[t] == INF) {
		re(i, nq)
			SQ[i].res = INF;
		return;
	}
	re(i, n)
	{
		dist2[i] = INF;
		vst[i] = 0;
	}
	dist2[t] = 0;
	q0.No = t;
	q0.d0 = 0;
	PQ.push(q0);
	while (!PQ.empty()) {
		x = PQ.top().No;
		PQ.pop();
		if (!vst[x]) {
			vst[x] = 1;
			for (int p = _E[x].next; p != x; p = _E[p].next) {
				y = _E[p].b;
				d0 = dist2[x] + _E[p].w;
				if (d0 < dist2[y]) {
					q0.d0 = dist2[y] = d0;
					q0.No = y;
					PQ.push(q0);
				}
			}
		}
	}
	re(i, n)
		vst[i] = 0;
	vst[s] = 1;
	Q[0] = s;
	DEP[s] = 0;
	for (int front = 0, rear = 0; front <= rear; front++) {
		x = Q[front];
		for (int p = _E[x].next; p != x; p = _E[p].next) {
			y = _E[p].b;
			if (dist[x] + _E[p].w == dist[y] && !vst[y]) {
				pr0[y] = p;
				pr[y] = m;
				add_edge(x, y, _E[p].w);
				DEP[y] = DEP[x] + 1;
				vst[y] = 1;
				Q[++rear] = y;
			}
		}
	}
	int maxdep = 0, z;
	re(i, n)
		vst[i] = 0;
	n0 = 0;
	for (x = t; x != s; x = E[pr[x]].a) {
		vst2[x] = 1;
		_E[pr0[x]].Z = _E[pr0[x] ^ 1].Z = 1;
		ts[n0++] = x;
	}
	ts[n0++] = s;
	vst2[s] = 1;
	int _;
	for (int front = 0, rear = n0 - 1; front < rear; front++, rear--) {
		_ = ts[front];
		ts[front] = ts[rear];
		ts[rear] = _;
	}
	re(i, n)
	{
		x = ts[i];
		if (maxdep < i)
			E[pr[x]].Z = 1;
		Q[0] = x;
		vst[x] = 1;
		for (int front = 0, rear = 0; front <= rear; front++) {
			y = Q[front];
			for (int p = _E[y].next; p != y; p = _E[p].next)
				if (!_E[p].Z) {
					z = _E[p].b;
					if (dist[y] + _E[p].w == dist[z] && !vst[z]) {
						vst[z] = 1;
						Q[++rear] = z;
						if (vst2[z] && DEP[z] > maxdep)
							maxdep = DEP[z];
					}
				}
		}
	}
	re(i, n)
		if (i == s)
			prs[i][0] = -1;
		else {
			prs[i][0] = E[pr[i]].a;
			_E[pr0[i]].Z = _E[pr0[i] ^ 1].Z = 1;
		}
	re2(j, 1, MAXS)
		re(i, n)
			if ((x = prs[i][j - 1]) == -1)
				prs[i][j] = -1;
			else
				prs[i][j] = prs[x][j - 1];
	re2(i, 1, n0 + n0)
		T[i] = INF;
}
int LCA(int x, int y) {
	if (DEP[x] > DEP[y]) {
		int _ = x;
		x = y;
		y = _;
	}
	int dep0 = DEP[y] - DEP[x];
	rre(i, MAXS)
		if ((1 << i) <= dep0) {
			y = prs[y][i];
			dep0 -= (1 << i);
		}
	if (x == y)
		return x;
	else {
		rre(i, MAXS)
			if (prs[x][i] != prs[y][i]) {
				x = prs[x][i];
				y = prs[y][i];
			}
		return E[pr[x]].a;
	}
}
void opr(int l, int r, int No) {
	if (l >= l0 && r <= r0) {
		if (v0 < T[No])
			T[No] = v0;
	} else {
		int mid = (l + r) >> 1;
		if (mid >= l0)
			opr(l, mid, LCH(No));
		if (mid < r0)
			opr(mid + 1, r, RCH(No, l, r));
	}
}
void visit(int l, int r, int No, ll minv) {
	ll minv0 = minv;
	if (T[No] < minv0)
		minv0 = T[No];
	if (l == r)
		res[l] = minv0;
	else {
		int mid = (l + r) >> 1;
		visit(l, mid, LCH(No), minv0);
		visit(mid + 1, r, RCH(No, l, r), minv0);
	}
}
void solve() {
	int x, y;
	re2(i, (n & 1 ? n + 1 : n), _m)
	{
		x = _E[i].a;
		y = _E[i].b;
		if (!_E[i].Z) {
			l0 = DEP[LCA(x, t)] + 1;
			r0 = DEP[LCA(y, t)];
			if (l0 <= r0) {
				v0 = dist[x] + _E[i].w + dist2[y];
				opr(0, n0 - 1, 1);
			}
		}
	}
	visit(0, n0 - 1, 1, INF);
	re(i, nq)
	{
		x = SQ[i].a;
		y = SQ[i].b;
		if (vst2[x] && vst2[y]) {
			if (DEP[x] + 1 == DEP[y] && E[pr[y]].Z)
				SQ[i].res = res[DEP[y]];
			else if (DEP[y] + 1 == DEP[x] && E[pr[x]].Z)
				SQ[i].res = res[DEP[x]];
			else
				SQ[i].res = dist[t];
		} else
			SQ[i].res = dist[t];
	}
}
void pri() {
	re(i, nq)
		if (SQ[i].res == INF)
			puts("Infinity");
		else
			cout << SQ[i].res << endl;
}
int main() {
	init();
	prepare();
	if (dist[t] != INF)
		solve();
	pri();
	return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
typedef struct{
  int u;
  long long w;
} node;
void sort_a(long long*a,int size);
void merge(long long*a,long long*left_a,long long*right_a,int left_size,int right_size);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size);
void heap_insert(node *heap,node *elem,int *size,int *heap_list);
void heap_update(node *heap,node *elem,int *heap_list);
void heap_read(node *heap,int *size,int *heap_list,node *ans);
int get_i(long long*a,long long num,int size);
long long med(long long*a,int size);
void range_increment(int i,int j,long long val,long long*tree,int N);
long long query(int i,long long*tree,int N);
void DJ(int N,int M,int*u,int*v,int*w,int*v_right,int*list_index,int*left_index,int*right_index,int S,long long*d,int*bridge,int*island);

int main(){
  int N,M,S,D,Q,x,y,p,f,b,i,j;
  int *u,*v,*w,*v_right,*list_index,*left_index,*right_index,*bridge,*island;
  long long *d_s,*d_d,*path,*bypass;
  scanf("%d%d",&N,&M);
  u=(int*)malloc(M*sizeof(int));
  v=(int*)malloc(M*sizeof(int));
  w=(int*)malloc(M*sizeof(int));
  v_right=(int*)malloc(M*sizeof(int));
  list_index=(int*)malloc(M*sizeof(int));
  left_index=(int*)malloc(M*sizeof(int));
  right_index=(int*)malloc(M*sizeof(int));
  d_s=(long long*)malloc(N*sizeof(long long));
  d_d=(long long*)malloc(N*sizeof(long long));
  bridge=(int*)malloc(M*sizeof(int));
  path=(long long*)malloc(M*sizeof(long long));
  island=(int*)malloc(N*sizeof(int));
  bypass=(long long*)malloc(M*3*sizeof(long long));
  for(i=0;i<M;i++){
    scanf("%d%d%d",u+i,v+i,w+i);
    list_index[i]=i;
    bridge[i]=0;
  }
  for(i=0;i<N;i++)
    d_s[i]=d_d[i]=-1;
  for(i=0;i<M*3;i++)
    bypass[i]=-1;
  sort_a3(u,v,w,M);
  for(i=0;i<M;i++)
    v_right[i]=v[i];
  sort_a2(v_right,list_index,M);
  for(i=0;i<M;i++){
    if(i==0 || u[i]!=u[i-1])
      left_index[u[i]]=i;
    if(i==0 || v_right[i]!=v_right[i-1])
      right_index[v_right[i]]=i;
  }
  scanf("%d%d%d",&S,&D,&Q);
  f=0;
  DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,S,d_s,bridge,island);
  DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,D,d_d,bridge,island);
  if(d_s[D]==-1)
    f=1;
  else{
    for(i=0,p=0;i<M;i++)
      if(d_s[u[i]]!=-1 && (d_s[u[i]]+d_d[v[i]]+w[i]==d_s[D] || d_s[v[i]]+d_d[u[i]]+w[i]==d_s[D])){
        bridge[i]=1;
        path[p]=(d_s[u[i]]>d_s[v[i]])?d_s[u[i]]:d_s[v[i]];
        p++;
      }
    sort_a(path,p);
    for(i=0,b=0;i<M;i++)
      if(bridge[i]){
        x=(d_s[u[i]]<d_s[v[i]])?d_s[u[i]]:d_s[v[i]];
        y=(d_s[u[i]]<d_s[v[i]])?d_s[v[i]]:d_s[u[i]];
        j=get_i(path,x,p);
        if(path[j]==y && (j==p-1 || path[j+1]>y)){
          bridge[i]=2;
          b++;
        }
      }
    for(i=0;i<N;i++)
      d_s[i]=island[i]=-1;
    DJ(N,M,u,v,w,v_right,list_index,left_index,right_index,S,d_s,bridge,island);
    for(i=0;i<M;i++)
      if(bridge[i]!=2){
        x=(island[u[i]]>island[v[i]])?island[v[i]]:island[u[i]];
        y=(island[u[i]]>island[v[i]])?island[u[i]]:island[v[i]];
        j=(island[u[i]]>island[v[i]])?d_s[v[i]]+w[i]+d_d[u[i]]:d_s[u[i]]+w[i]+d_d[v[i]];
        range_increment(x+1,y,j,bypass,b);
      }
  }
  while(Q--){
    scanf("%d%d",&x,&y);
    if(f)
      printf("Infinityn");
    else{
      for(i=left_index[x];i>=0 && i<M && u[i]==x;i++)
        if(v[i]==y)
          if(bridge[i]==2)
            if(query((island[u[i]]>island[v[i]])?island[v[i]]+1:island[u[i]]+1,bypass,b)==-1)
              printf("Infinityn");
            else
              printf("%lldn",query((island[u[i]]>island[v[i]])?island[v[i]]+1:island[u[i]]+1,bypass,b));
          else
            printf("%lldn",d_s[D]);
      for(i=right_index[x];i>=0 && i<M && v_right[i]==x;i++)
        if(u[list_index[i]]==y)
          if(bridge[list_index[i]]==2)
            if(query((island[u[list_index[i]]]>island[v[list_index[i]]])?island[v[list_index[i]]]+1:island[u[list_index[i]]]+1,bypass,b)==-1)
              printf("Infinityn");
            else
              printf("%lldn",query((island[u[list_index[i]]]>island[v[list_index[i]]])?island[v[list_index[i]]]+1:island[u[list_index[i]]]+1,bypass,b));
          else
            printf("%lldn",d_s[D]);
    }
  }
  return 0;
}
void sort_a(long long*a,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  long long *left_a,*right_a;
  left_a=(long long*)malloc(m*sizeof(long long));
  right_a=(long long*)malloc((size-m)*sizeof(long long));
  for(i=0;i<m;i++)
    left_a[i]=a[i];
  for(i=0;i<size-m;i++)
    right_a[i]=a[i+m];
  sort_a(left_a,m);
  sort_a(right_a,size-m);
  merge(a,left_a,right_a,m,size-m);
  free(left_a);
  free(right_a);
  return;
}
void merge(long long*a,long long*left_a,long long*right_a,int left_size,int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      j++;
    }
  }
  return;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size,int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}
void sort_a3(int*a,int*b,int*c,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  left_c=(int*)malloc(m*sizeof(int));
  right_c=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
    left_c[i]=c[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
    right_c[i]=c[i+m];
  }
  sort_a3(left_a,left_b,left_c,m);
  sort_a3(right_a,right_b,right_c,size-m);
  merge3(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  free(left_c);
  free(right_c);
  return;
}
void merge3(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size,int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      c[i+j] = left_c[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      c[i+j] = right_c[j];
      j++;
    }
  }
  return;
}
void heap_insert(node *heap,node *elem,int *size,int *heap_list){
  (*size)++;
  int index=(*size);
  while(index>1 && elem->w<heap[index/2].w){
    heap[index]=heap[index/2];
    heap_list[heap[index].u]=index;
    index/=2;
  }
  heap[index]=(*elem);
  heap_list[elem->u]=index;
  return;
}
void heap_update(node *heap,node *elem,int *heap_list){
  int index=heap_list[elem->u];
  while(index>1 && elem->w<heap[index/2].w){
    heap[index]=heap[index/2];
    heap_list[heap[index].u]=index;
    index/=2;
  }
  heap[index]=(*elem);
  heap_list[elem->u]=index;
  return;
}
void heap_read(node *heap,int *size,int *heap_list,node *ans){
  (*ans)=heap[1];
  int index=1;
  while(index*2<*size && heap[*size].w>heap[index*2].w || index*2+1<*size && heap[*size].w>heap[index*2+1].w){
    index=(heap[index*2].w>heap[index*2+1].w)?index*2+1:index*2;
    heap[index/2]=heap[index];
    heap_list[heap[index].u]=index/2;
  }
  heap[index]=heap[*size];
  heap_list[heap[index].u]=index;
  (*size)--;
  return;
}
int get_i(long long*a,long long num,int size){
  if(size==0)
    return 0;
  if(num>=med(a,size))
    return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
  else
    return get_i(a,num,(size-1)>>1);
}
long long med(long long*a,int size){
  return a[(size-1)>>1];
}
void range_increment(int i,int j,long long val,long long*tree,int N){
  for(i+=N,j+=N;i<=j;i=(i+1)/2,j=(j-1)/2){
    if(i%2 && (tree[i]==-1 || tree[i]>val)) tree[i] = val;
    if(j%2==0 && (tree[j]==-1 || tree[j]>val)) tree[j] = val;
  }
  return;
}
long long query(int i,long long*tree,int N){
  long long ans=-1,j;
  for(j = i + N; j; j /= 2)
    if(ans==-1 || ans>tree[j] && tree[j]!=-1)
      ans=tree[j];
  return ans;
}
void DJ(int N,int M,int*u,int*v,int*w,int*v_right,int*list_index,int*left_index,int*right_index,int S,long long*d,int*bridge,int*island){
  int i,next_solve,heap_size=0,*heap_list,island_num;
  node elem,*heap;
  heap=(node*)malloc(N*sizeof(node));
  heap_list=(int*)malloc(N*sizeof(int));
  d[S]=0;
  island[S]=0;
  next_solve=S;
  while(1){
    for(i=left_index[next_solve];i>=0 && i<M && u[i]==next_solve;i++)
      if(d[v[i]]==-1 || d[v[i]]>d[next_solve]+w[i]){
        elem.u=v[i];
        elem.w=d[next_solve]+w[i];
        if(d[v[i]]==-1)
          heap_insert(heap,&elem,&heap_size,heap_list);
        else
          heap_update(heap,&elem,heap_list);
        d[v[i]]=d[next_solve]+w[i];
        if(bridge[i]==2)
          island[v[i]]=island[next_solve]+1;
        else
          island[v[i]]=island[next_solve];
      }
      else if(d[v[i]]==d[next_solve]+w[i]){
        if(bridge[i]==2)
          island_num=island[next_solve]+1;
        else
          island_num=island[next_solve];
        if(island[v[i]]>island_num)
          island[v[i]]=island_num;
      }
    for(i=right_index[next_solve];i>=0 && i<M && v_right[i]==next_solve;i++)
      if(d[u[list_index[i]]]==-1 || d[u[list_index[i]]]>d[next_solve]+w[list_index[i]]){
        elem.u=u[list_index[i]];
        elem.w=d[next_solve]+w[list_index[i]];
        if(d[u[list_index[i]]]==-1)
          heap_insert(heap,&elem,&heap_size,heap_list);
        else
          heap_update(heap,&elem,heap_list);
        d[u[list_index[i]]]=d[next_solve]+w[list_index[i]];
        if(bridge[list_index[i]]==2)
          island[u[list_index[i]]]=island[next_solve]+1;
        else
          island[u[list_index[i]]]=island[next_solve];
      }
      else if(d[u[list_index[i]]]==d[next_solve]+w[list_index[i]]){
        if(bridge[list_index[i]]==2)
          island_num=island[next_solve]+1;
        else
          island_num=island[next_solve];
        if(island[u[list_index[i]]]>island_num)
          island[u[list_index[i]]]=island_num;
      }
    if(heap_size==0)
      break;
    heap_read(heap,&heap_size,heap_list,&elem);
    next_solve=elem.u;
  }
  free(heap);
  free(heap_list);
  return;
}