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

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