Page 2 of 5

10986 - Sending email

Posted: Tue Feb 07, 2006 12:00 am
by ErickNascimento
I dont know why my program get WA after WA, can anybody who gets acc help me?
Is there any trick in the input?
Give some inputs for this, please!

here is my code:

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;	
}

Posted: Tue Feb 07, 2006 5:58 am
by rushel
watch ur heap implementaion . I use bfs and adjaceny list at contest time.

Posted: Tue Feb 07, 2006 8:26 am
by sohel
I used bfs, but maintained a priority_queue instead of the conventional queue.

when i used the conv. queue, my AC time was 2.xxx seconds, but later shifting it to p_Q, the time came down significantly... 0.865 seconds.

Posted: Tue Feb 07, 2006 5:50 pm
by ErickNascimento
How did you used BFS in a unweighted graph?

Posted: Tue Feb 07, 2006 5:51 pm
by ErickNascimento
How did you used BFS in a unweighted graph?

Posted: Tue Feb 07, 2006 6:24 pm
by Abednego
I think he means "forgetting BFS", where you can add vertices to the queue multiple times, once for each time you improve its depth. It runs in O(n^3) time.

yeap..

Posted: Wed Feb 08, 2006 11:36 am
by sohel
Igor wrote: I think he means "forgetting BFS", where you can add vertices to the queue multiple times, once for each time you improve its depth. It runs in O(n^3) time.
Yes, something very similar to that..
.. This method is also known as 'exhaustive bfs'.

But suprisingly, this method produces better result than dijkstra, in terms of effieciency.

I can't remember the last time I used dijkstra to solve a problem, I invariably use 'exhaustive bfs'.

the searching is done using breadth first, as opposed to depth first.

Posted: Wed Feb 08, 2006 12:27 pm
by little joey
It works good in cases where the length of a path is proportional to the number of steps in the path, because this reduces the chance of 'rediscovering' a node in more steps but with shorter distance. The ultimate case is the square grid (cubic grid and higher dimensional pendants), where discovering a node means you found a shortest path to that node, so every node gets added to the queue only once. This is also known as flood-fill. Geometrical grids with evenly distributed nodes are also good candidates for this method.

Seeking Faster Solution without using STL

Posted: Fri Feb 17, 2006 8:31 am
by mrahman
I have solved this problem with my own written Priority Queue(Without using STL). My timing is so poor(Almost Last in Ranklist). How can I speed up my solution without using STL.

Thanks in Advance

Posted: Sat Feb 18, 2006 5:06 am
by wook
well, I also did not use STL. I wrote my own writeen PQ - a heap.

I think your implementation into source-code is not efficient enough, maybe.
Optimization is required, or, get rid of inefficiency-making-elements.

STL + priority_queue != AC ?

Posted: Mon Jul 31, 2006 7:24 am
by smilitude
:oops: :oops: :oops: :oops: :oops:
Can you tell me plz, why its giving me WA?

Code: Select all

    CUT AFTER AC.. THNX TO asif_rahman0

Posted: Mon Jul 31, 2006 12:13 pm
by asif_rahman0
watch it:

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; } 
are you compile your code yet?? or just cut and paste??
and now, look at below:

Code: Select all

....
#define INF 1<<30
..
.
if(nodes[t].mdist==INF)
            printf("Case #%d: unreachable\n",++cases);
...
hope both of this help you. ;)
bye
rabbi

Posted: Mon Jul 31, 2006 12:45 pm
by smilitude
Oh man! thanks a lottttttttt!
I just forgot to return! but somehow my gcc compiler didnt show any error!

How silly that can be!
:oops: :oops: :oops: :oops: :oops: :oops: :oops:

in need of some tricky test cases:

Posted: Sat Nov 18, 2006 6:24 pm
by nymo
Hi, Can anyone provide some tricky test cases... I am getting WA. I am using dijkstra's shortest path algorithm... thanks.

EDIT: One more thing: Is it possible that there may be multiple edges between the same pair of nodes with different cost... i.e. a b 20 and a b 10?

Posted: Sun Nov 26, 2006 8:26 pm
by asif_rahman0
No multiple edges. Clear cut dijkstra with Priority Queue.
And Input below:(not tricky)

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
Output:

Code: Select all

Case #1: 13
Case #2: 13
Case #3: 11
Case #4: 8
Also you can check your cost[]....assigned it to big value ...like: 1<<30
bye
rabbi