I implemented it using min_heap instead of using built in priority queue. Test case 32 is very long and it is hard to guess. Please give me a test case which my code would fail:
vector<int> edge[100002];
vector<int> cost[100002];
int par[100002];
long long dis[100002];
struct customDataType {
int node;
long long mincost;
customDataType() {}
customDataType(int x,long long y) {
node=x;
mincost=y;
}
};
customDataType heapArr[3000001];
bool heapEmpty() {
return heapArr[1].node==INT_MAX;
}
void push_heap(int node,long long cst,int& index) {
if(heapArr[index].node!=INT_MAX)
index++;
heapArr[index]=customDataType(node,cst);
int i=index;
while(i/2>=1 && heapArr[i/2].mincost>heapArr[i].mincost) {
swap(heapArr[i/2],heapArr[i]);
i/=2;
}
index++;
}
void pop_heap(int& index) {
if(heapArr[index].node==INT_MAX)
index--;
heapArr[1]=heapArr[index];
heapArr[index]=customDataType(INT_MAX,INT_MAX); ///deleted
int i=1;
while(min(heapArr[i*2].node,heapArr[i*2+1].node)!=INT_MAX && min(heapArr[i*2].mincost,heapArr[i*2+1].mincost)<heapArr[i].mincost) {
if(min(heapArr[i*2].mincost,heapArr[i*2+1].mincost)==heapArr[i*2].mincost) {
swap(heapArr[i*2],heapArr[i]);
i*=2;
} else {
swap(heapArr[i*2+1],heapArr[i]);
i=i*2+1;
}
}
index--;
}
void dijkstra(int src) {
int curr=1;
dis[src]=0;
push_heap(src,dis[src],curr);
while(!heapEmpty()) {
customDataType U=heapArr[1];
pop_heap(curr); /// curr is the last inserted value .
for(int i=0; i<edge[U.node].size(); i++) {
int V=edge[U.node][i];
long long dstance=U.mincost+cost[U.node][i];
if(dis[V]>dstance) {
dis[V]=dstance;
par[V]=U.node;
if(curr==0) /// priority queue is now empty , so start from 1.
curr=1;
push_heap(V,dis[V],curr);
}
}
}
}
void path_print(int u) {
if(u==1) {
printf("%d ",u);
return;
}
path_print(par[u]);
printf("%d ",u);
}
void debug(int n){
puts("");
puts("");
for(int i=1;i<=n;i++){
printf("%d: ",i);
for(int u: edge[i])
printf("%d ",u);
puts("");
}
puts("");
for(int i=1;i<=n;i++){
printf("%d: ",i);
for(int u: cost[i])
printf("%d ",u);
puts("");
}
}
int main() {
int n,m,u,v,w;
while(cin>>n>>m) {
for(int i=1; i<3000001; i++) {
heapArr[i].node=INT_MAX;
}
for(int i=1;i<100002;i++){
dis[i]=LLONG_MAX;
edge[i].clear();
cost[i].clear();
}
while(m--) {
scanf("%d %d %d",&u,&v,&w);
edge[u].push_back(v);
cost[u].push_back(w);
edge[v].push_back(u);
cost[v].push_back(w);
}
// debug(n);
dijkstra(1);
if(dis[n]==LLONG_MAX)
puts("-1");
else {
path_print(n);
printf("\n");
}
}
return 0;
}