Dijkstra Algorithm

 
#include
#include
#define inf 1000000000
#define SIZE1 20000
#define SIZE2 50000
using namespace std;
typedef vectorgraph;
long Q[SIZE1+9],d[SIZE1+9],positionOf[SIZE1+9];
graph G[SIZE2*2+9],W[SIZE2*2+9];
//posiotionOf[]= posiontion of one node in Q[] or tree
//Q[] is a tree or collection of nodes in priority sequences.
//d[]= the minimum values to reach in nodes. 

int min_heapify(long i,long n){
	long temp,minimum,l,r;
	l=2*i;
	r=2*i+1;
	if(l<=n && d[Q[l]]d[Q[i]]){
			temp=Q[i/2];
			Q[i/2]=Q[i];
			Q[i]=temp;		
			positionOf[Q[i]]=i;
			positionOf[Q[i/2]]=i/2;		
			i=i/2;
		}
		else
			break;		
	}
	return 0;
}
int main(){
	long i,j,n,m,u,v,w,source,dest,t;	
	scanf("%ld",&t);
	for(j=1;j<=t;j++){		
		scanf("%ld%ld%ld%ld",&n,&m,&source,&dest);
		for(i=1;i<=n;i++){
			G[i].clear();
			W[i].clear();
			d[i]=inf;
			Q[i]=i;
			positionOf[i]=i;
		}
		for(i=1;i<=m;i++){
			scanf("%ld%ld%ld",&u,&v,&w);
			G[u+1].push_back(v+1);
			G[v+1].push_back(u+1);
			W[u+1].push_back(w);
			W[v+1].push_back(w);
		}		
		d[source+1]=0;update_min_heap(source+1);
		while(n>0)
		{
			u=extract_min_Q(n);
			n--;
			for(v=0;v1)
					{
						update_min_heap(positionOf[G[u][v]]);
					}

				}
			}			
		}		
		if(d[dest+1]==inf)
			printf("Case #%ld: unreachable\n",j);
		else
			printf("Case #%ld: %ld\n",j,d[dest+1]);
	}
	return 0;
}