10986 - Sending email

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ErickNascimento
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm

10986 - Sending email

Post by ErickNascimento » Tue Feb 07, 2006 12:00 am

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
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Tue Feb 07, 2006 5:58 am

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Feb 07, 2006 8:26 am

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
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm

Post by ErickNascimento » Tue Feb 07, 2006 5:50 pm

How did you used BFS in a unweighted graph?

ErickNascimento
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm

Post by ErickNascimento » Tue Feb 07, 2006 5:51 pm

How did you used BFS in a unweighted graph?

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Feb 07, 2006 6:24 pm

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.
If only I had as much free time as I did in college...

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

yeap..

Post by sohel » Wed Feb 08, 2006 11:36 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Feb 08, 2006 12:27 pm

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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Seeking Faster Solution without using STL

Post by mrahman » Fri Feb 17, 2006 8:31 am

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
Practice Makes a man perfect

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Sat Feb 18, 2006 5:06 am

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.
Sorry For My Poor English.. :)

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

STL + priority_queue != AC ?

Post by smilitude » Mon Jul 31, 2006 7:24 am

: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
Last edited by smilitude on Mon Jul 31, 2006 12:58 pm, edited 1 time in total.
fahim
#include <smile.h>

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Mon Jul 31, 2006 12:13 pm

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

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Mon Jul 31, 2006 12:45 pm

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:
fahim
#include <smile.h>

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

in need of some tricky test cases:

Post by nymo » Sat Nov 18, 2006 6:24 pm

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?
regards,
nymo

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Sun Nov 26, 2006 8:26 pm

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
Last edited by asif_rahman0 on Mon Nov 27, 2006 1:39 am, edited 1 time in total.

Post Reply

Return to “Volume 109 (10900-10999)”