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