蒟蒻求援

P1462 通往奥格瑞玛的道路

人中 @ 2019-08-23 21:53:00


int check(int x) {
    if(x<money[1])
        return 0;
    for(int i=1; i<=n; i++) {
        dist[i]=0x3f3f3f3f3f;
    }
    dist[1]=0;
    Q.push((node) {
        1,0
    });
    while(!Q.empty()) {
        node fr=Q.top();
        Q.pop();
        int d=fr.d;
        int u=fr.u;
        if(dist[u]!=d)
        continue;
        for(int i=head[u]; i; i=edge[i].next) {
            if(dist[edge[i].to]>edge[i].dis+dist[u]&&money[edge[i].to]<=x) {    
                dist[edge[i].to]=edge[i].dis+dist[u];
                Q.push((node {edge[i].to,dist[edge[i].to]}));
            }
            if(edge[i].to==n) {
                if(dist[n]<=hp)
                    return 1;
                    else
                return 0;
            }
        }
    }
}

    while(l<r){
    int mid=(l+r)>>1;
        if(check(mid)==1) {r=mid;kl=1;
        }
        else l=mid+1;
    }
    if(kl==0){
         cout<<"AFK";
    }else
    cout<<l;
}

这是我的二分和check函数

为什么 我将

for(int i=head[u]; i; i=edge[i].next) {
            if(dist[edge[i].to]>edge[i].dis+dist[u]&&money[edge[i].to]<=x) {    

写成

for(int i=head[u]; i; i=edge[i].next) {
 if(money[i]>x)
continue;
if(dist[edge[i].to]>edge[i].dis+dist[u]) {  

就错了

麻烦@一下我,蟹蟹


by 顾小伍 @ 2019-08-26 20:26:28

@人中 i表示的是这条边指向的节点位置,不能直接表示所指的节点,所以要把i改成edge[i].to,这是链式前向星的基本常识。最后安利一波我的博客,喜欢可以点个赞~(≧▽≦)/~


by 人中 @ 2019-08-26 20:38:52

@顾小伍 啊啊蟹蟹,错误好低级,丢脸


by 顾小伍 @ 2019-08-26 20:44:21

@人中 初学是比较容易错,很正常的事


|