dijk板子改了一晚上，帮忙看看吧

wangyansong @ 2020-10-29 21:40:25

#include<bits/stdc++.h>
using namespace std;
#define maxn 1001000
#define inf 0x3f3f3f3f
int n,m,hp,dis[maxn],head[maxn],c[maxn],b[maxn],vis[maxn],cnt;
struct edge{
    int v,next,w;
}e[maxn];
struct node{
    int w,now;
    inline bool operator<(const node &x)const{
        return w>x.w;
        }
};
inline int add(int x,int y,int w){
    e[++cnt].v=y;
    e[cnt].w=w;
    e[cnt].next=head[x];
    head[x]=cnt;
}
inline int read(){
    int x=0,k=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')k=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*k;
}
priority_queue<node> q;
void check(int x)
{
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    dis[1]=0;
    while(!q.empty())q.pop();
    q.push((node){0,1});
    while(!q.empty()){
        node x=q.top();q.pop();
        int u=x.now;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    q.push((node){dis[v],v});
                }
            }
        }
    }
//  cout<<dis[n];
}
int main()
{
    n=read(),m=read(),hp=read();
    int l=1,r=0,mid,ans=0;
    for(int i=1;i<=n;++i){
        scanf("%d",b+i);//,c[i]=b[i];
        r=max(r,b[i]);
    }
    l=max(b[1],b[n]);
//  cout<<l<<" "<<r<<endl;
    for(int i=1;i<=m;++i){
        int x,y,z;
        x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,z);
    }
//  sort(c+1,c+n+1);
    while(l<r){
    //  cout<<mid<<" ";
        mid=(l+r)>>1;
        check(mid);
        if(dis[mid]>hp)l=mid+1;
        else r=mid;
    }
    check(1);
    if(dis[n]>hp) cout<<"AFK";
    else cout<<l;
}

by wangyansong @ 2020-10-29 21:48:12

#include<bits/stdc++.h>
using namespace std;
#define maxn 1001000
#define inf 0x3f3f3f3f
int n,m,hp,dis[maxn],head[maxn],c[maxn],b[maxn],vis[maxn],cnt;
struct edge{
    int v,next,w;
}e[maxn];
struct node{
    int w,now;
    inline bool operator<(const node &x)const{
        return w>x.w;
        }
};
inline int add(int x,int y,int w){
    e[++cnt].v=y;
    e[cnt].w=w;
    e[cnt].next=head[x];
    head[x]=cnt;
}
inline int read(){
    int x=0,k=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')k=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*k;
}
priority_queue<node> q;
bool check(int xx)
{
    if(xx<c[1]||xx<c[n]) return 0;
    memset(vis,0,sizeof(vis));
    memset(dis,inf,sizeof(dis));
    dis[1]=0;
    q.push((node){0,1});
    while(!q.empty()){
        node x=q.top();q.pop();
        int u=x.now;
        if(vis[u])continue;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].v;
            if(xx<b[v]) continue;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
        //      if(!vis[v]){
                    q.push((node){dis[v],v});
    //          }
            }
        }
    }
    return dis[n]<=hp;
}
int main()
{
    n=read(),m=read(),hp=read();
    for(int i=1;i<=n;++i)
    b[i]=read(),c[i]=b[i];
    for(int i=1;i<=m;++i){
        int x,y,z;
        x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,z);
    }
    sort(c+1,c+n+1);
    if(!check(c[n])){
        cout<<"AFK";
        return 0;
    }
    int l=1,r=maxn,mid,ans=c[n];
    while(l<=r){
        mid=(l+r)>>1;
        if(check(c[mid]))r=mid-1,ans=c[mid];
        else l=mid+1;
    }
    cout<<ans;
}

by Bitter_Tea @ 2020-10-29 21:48:30

最后入堆的判断条件

by wangyansong @ 2020-10-29 21:48:46

这是改过的

by wangyansong @ 2020-10-29 21:49:52

@Bitter_Tea 大佬判断什么啊？一开始我加的vis

by zmza @ 2020-10-29 21:53:48

@wangyansong 你的memset赋值赋错了。inf应该为0x3f

by 无咕_ @ 2020-10-29 22:02:06

@wangyansong 有以下几个问题：

1.数组开太大了，边数组开1e5+9，其他开1e4+9就行、

2.Dij写错了，将

for(int i=head[u];i;i=e[i].next){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    q.push((node){dis[v],v});
                }
            }
        }

改为

for(int i=head[u];i;i=e[i].next){
    int v=e[i].v;
    if(money[to]>maxn)continue;
    if(dis[v]>dis[u]+e[i].w){
        dis[v]=dis[u]+e[i].w;
        q.push((priority){to,dis[to]});
    }
}

3.建边的时候最好加一条if(from==to)continue;，节省空间时间

4.将if(dis[mid]>hp)l=mid+1;改为if(dis[n]>hp)l=mid+1;

by 无咕_ @ 2020-10-29 22:03:53

我上面那条该下。。。

第2条我改的改成：

for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(money[v]>maxn)continue;
if(dis[v]>dis[u]+e[i].w){
    dis[v]=dis[u]+e[i].w;
    q.push((priority){to,dis[v]});
}
}

by wangyansong @ 2020-10-30 10:11:12

@无咕_ 谢谢您，改过了，会RE

by wangyansong @ 2020-10-30 10:11:45

@张茗祖 好像没什么效果

by wangyansong @ 2020-10-31 17:21:22

提交43次，错在```c if(dis[to]>dis[temp]+wr&&c[to]<=top)

是a【to】不是c【to】