daihan's blog

By daihan, 5 years ago, In English

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;
}
  • Vote: I like it
  • -21
  • Vote: I do not like it