## 10986 - Sending email

Moderator: Board moderators

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

### 10986 - Sending email

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

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];
pVertice Q[MAX_VERTICES]; //heap min-priority queue
int nQ; //number of elements in Q
int u_id;

// 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);

for(l=0;l<n;l++)

for(l=0;l<m;l++){
scanf("%d %d %d", &a, &b, &w);
}

/* 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;

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
watch ur heap implementaion . I use bfs and adjaceny list at contest time.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
How did you used BFS in a unweighted graph?

ErickNascimento
New poster
Posts: 6
Joined: Fri Dec 16, 2005 11:40 pm
How did you used BFS in a unweighted graph?

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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...

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

### yeap..

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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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
Contact:

### Seeking Faster Solution without using STL

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.

Practice Makes a man perfect

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
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..

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

### STL + priority_queue != AC ?

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
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);
...
``````
bye
rabbi

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am
Oh man! thanks a lottttttttt!
I just forgot to return! but somehow my gcc compiler didnt show any error!

How silly that can be!
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:

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