Page 2 of 5

### 10986 - Sending email

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

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

//clear the adjacency lists
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;
}
``````

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

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

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

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

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

### yeap..

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

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

### Seeking Faster Solution without using STL

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

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

### STL + priority_queue != AC ?

Posted: Mon Jul 31, 2006 7:24 am

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

Posted: 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!

### in need of some tricky test cases:

Posted: 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?

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