10986 - Sending email

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

[rushel]

watch ur heap implementaion . I use bfs and adjaceny list at contest time.

[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.

[ErickNascimento]

How did you used BFS in a unweighted graph?

[ErickNascimento]

How did you used BFS in a unweighted graph?

[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.

[sohel]

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.

[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.

[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

[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.

[smilitude]

Can you tell me plz, why its giving me WA?

Code: Select all

    CUT AFTER AC.. THNX TO asif_rahman0

[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

[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!

[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?

[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