OJ Board

Code: Select all

#include <cstdio>
#include <queue>
#include <vector>
#include <list>
#include <algorithm>
#include <limits.h>

using namespace std;

#define MAX_VERTICES 20100
#define MY_INT_MAX (UINT_MAX/2)

struct vertice{
	int id;
	unsigned int d; //estimate distance from source
};

struct adj_weight{
	int id; //id of incidented vertice
	int w;  //weight of the incident edge 
};

struct pVertice{
	vertice *p;
};

bool operator< (pVertice u, pVertice v){
	return (u.p)->d > (v.p)->d;
}

int N;
int n, m, S, T;
int k, l, i, j;
int a, b, w;

vertice v[MAX_VERTICES];
vector<list<adj_weight> > adj(MAX_VERTICES);
pVertice Q[MAX_VERTICES]; //heap min-priority queue
int nQ; //number of elements in Q
adj_weight tmp; //read the edges
int u_id;
list<adj_weight>::iterator it;

// i: id of the element in heap Q
void SobeHeap(int i){
	pVertice tmp;	
	while(i>0 && (Q[(i-1)/2].p->d > Q[i].p->d)){
		tmp=Q[i];
		Q[i]=Q[(i-1)/2];
		Q[(i-1)/2]=tmp;
		i=(i-1)/2;
	}
}

int main(){	
	scanf("%d", &N);
	
	for(k=0;k<N;k++){
		scanf("%d %d %d %d", &n, &m, &S, &T);
		
		//clear the adjacency lists
		for(l=0;l<n;l++)
			adj[l].clear();
		
		for(l=0;l<m;l++){
			scanf("%d %d %d", &a, &b, &w);
			tmp.id=b; tmp.w=w;	adj[a].push_back(tmp);
			tmp.id=a; 				  adj[b].push_back(tmp);
		}
		
		/* Dijkstra using binary heap min priority-queue (Complexity: O(V*V)) */
		
		//initialize_single_source
		for(i=0;i<n;i++){
			v[i].id = i;
			v[i].d = MY_INT_MAX;
			Q[i].p=&v[i];
		}
		v[S].d = 0;
						
  	//Q:=Vertices(G) /* Put the vertices in a PQ */
		nQ = n;
		make_heap(Q, Q + nQ);	
			
		//while not Empty(Q)
		while(nQ > 0){
			u_id = Q[0].p->id;
			pop_heap(Q, Q + nQ);
			nQ--;
			
			//*Optimization*
			if(u_id == T)
				break;			
			
			for(it=adj[u_id].begin(); it!=adj[u_id].end(); it++)
				if(v[(*it).id].d > v[u_id].d+(*it).w){
					v[(*it).id].d = v[u_id].d+(*it).w;
					SobeHeap((*it).id);
				}
		}
		if(v[T].d == MY_INT_MAX)
			printf("Case #%d: unreachable\n", k+1);
		else
			printf("Case #%d: %u\n", k+1, v[T].d);
	
	}		
	return 0;	
}

Code: Select all

    CUT AFTER AC.. THNX TO asif_rahman0

Code: Select all

inline bool operator<(dnode a, dnode b) { a.ddist>b.ddist; }
inline bool operator>(dnode a, dnode b) { a.ddist<b.ddist; } 

Code: Select all

....
#define INF 1<<30
..
.
if(nodes[t].mdist==INF)
            printf("Case #%d: unreachable\n",++cases);
...

Code: Select all

4
6 9 5 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 0 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 0 
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

Code: Select all

Case #1: 13
Case #2: 13
Case #3: 11
Case #4: 8