Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么这个Dijkstra+heap会WA

Posted by leeleeon at 2012-07-26 22:34:38 on Problem 3159
#include<cstdio>
#define maxn 30001
using namespace std;
struct link
{
    int nd,wei;
    link* nx;
};
link* G[maxn];
int d[maxn],hp[maxn],hpos[maxn],n,m,hsize;
void add(int a,int b,int w)
{
    link* p=new link;
    p->nd=b;p->wei=w;p->nx=G[a];G[a]=p;
}
void swap(int a,int b)
{
    int t=hp[a];hp[a]=hp[b];hp[b]=t;
    hpos[hp[a]]=a;hpos[hp[b]]=b;
}
void up(int L)
{
    int p=L>>1;
    while((p>0)&&(d[hp[L]]<d[hp[p]])) {
        swap(L,p);
        L=p;p=L<<1;
    }
}
void down(int L)
{
    int left,right,min;
    do {
        left=L<<1;right=left+1;
        if((left<=hsize)&&(d[hp[left]]<d[hp[L]])) min=left; else min=L;
        if((right<=hsize)&&(d[hp[right]]<d[hp[min]])) min=right;
        if (min==L) return ;
        swap(L,min);
        L=min;
    }while(1);
}
void makegraph()
{
    int a,b,c,i;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++) {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
}
int main()
{
    makegraph();
    int i,t,max;
    link* L;
    for (i=1;i<=n;i++) {
        hp[i]=i;hpos[i]=i;d[i]=0x7FFFFFFF;
    }
    d[1]=0;
    hsize=n;
    for(i=1;i<n;i++) {
        t=hp[1];hp[1]=hp[hsize--];down(1);
        for(L=G[t];L!=NULL;L=L->nx) {
            if (d[t]+L->wei<d[L->nd]) {
                d[L->nd]=d[t]+L->wei;
                up(hpos[L->nd]);
            }
        }
    }
    for(max=0,i=1;i<=n;i++) if (d[i]>max) max=d[i];
    printf("%d\n",max);
    return 0;
}
自己拿pascalA掉了,改成c++就WA

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator