63求助（WA6,8,10,11）

风中の菜鸡 @ 2021-11-28 14:34:29

#include<bits/stdc++.h>
using namespace std;
int n,m,b,num_edge,ans;
int q[10001],head[100010],qqq[10001];
struct Edge{
    int to,net,z;
}edge[100010];
void add_edge(int from,int to,int z){
    edge[++num_edge].net=head[from];
    edge[num_edge].to=to;
    edge[num_edge].z=z;
    head[from]=num_edge;
}
priority_queue<pair<int,int> >p;
int dis[10010],vis[10010];
bool cheak(int s){
    if(q[1]>s||q[n]>s)
        return false;
    for(int i=1;i<=n;i++){
        if(q[i]>s)
            vis[i]=1;
        else
            vis[i]=0;       
    }
    for(int i=1;i<=n;i++)
        dis[i]=1000000010;
    dis[1]=0;
    p.push(make_pair(1,0));
    while(!p.empty()){
        int tmp=p.top().first;
        p.pop();
        if(vis[tmp]==1)
            continue;
        vis[tmp]=1;
        for(int i=head[tmp];i;i=edge[i].net){
            int qq=edge[i].z,tt=edge[i].to;
            if(qq+dis[tmp]<dis[tt]){
                dis[tt]=qq+dis[tmp];
                p.push(make_pair(tt,-dis[tt]));         
            }
        }
    }
    if(dis[n]>b)
        return false;
    else
        return true;
}
int main(){
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++){
        cin>>q[i];
        qqq[i]=q[i];
    }
    for(int i=1;i<=m;i++){
        int aa,bb,cc;
        cin>>aa>>bb>>cc;
        if(aa==bb)
            continue;
        add_edge(aa,bb,cc);
        add_edge(bb,aa,cc);
    }   
    sort(qqq+1,qqq+n+1);
    if(cheak(qqq[n])==false){
        cout<<"AFK";
        return 0;
    }
    int l=1,mid,r=n;
    ans=qqq[n];
    while(l<=r){
        mid=(l+r)/2;
        if(cheak(qqq[mid])){
            r=mid-1;
            ans=qqq[mid];
        }
        else{
            l=mid+1;
        }   
        }
        cout<<ans;
    return 0;
}

by lucky叶 @ 2021-11-28 14:55:50

优先队列写错了

by lucky叶 @ 2021-11-28 14:56:46

第一项应该是值，第二项才是第几个

by lucky叶 @ 2021-11-28 14:58:19

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m,b,num_edge,ans;
int q[10001],head[100010],qqq[10001];
struct Edge{
    int to,net,z;
}edge[100010];
void add_edge(int from,int to,int z){
    edge[++num_edge].net=head[from];
    edge[num_edge].to=to;
    edge[num_edge].z=z;
    head[from]=num_edge;
}
priority_queue<pair<int,int> >p;
int dis[10010],vis[10010];
bool cheak(int s){
    if(q[1]>s||q[n]>s)
        return false;
    for(int i=1;i<=n;i++){
        if(q[i]>s)
            vis[i]=1;
        else
            vis[i]=0;       
    }
    for(int i=1;i<=n;i++)
        dis[i]=1000000010;
    dis[1]=0;
    p.push(make_pair(0,1));//here
    while(!p.empty()){
        int tmp=p.top().second;//here
        p.pop();
        if(vis[tmp]==1)
            continue;
        vis[tmp]=1;
        for(int i=head[tmp];i;i=edge[i].net){
            int qq=edge[i].z,tt=edge[i].to;
            if(qq+dis[tmp]<dis[tt]){
                dis[tt]=qq+dis[tmp];
                p.push(make_pair(-dis[tt],tt));//here      
            }
        }
    }
    if(dis[n]>b)
        return false;
    else
        return true;
}
int main(){
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++){
        cin>>q[i];
        qqq[i]=q[i];
    }
    for(int i=1;i<=m;i++){
        int aa,bb,cc;
        cin>>aa>>bb>>cc;
        if(aa==bb)
            continue;
        add_edge(aa,bb,cc);
        add_edge(bb,aa,cc);
    }   
    sort(qqq+1,qqq+n+1);
    if(cheak(qqq[n])==false){
        cout<<"AFK";
        return 0;
    }
    int l=1,mid,r=n;
    ans=qqq[n];
    while(l<=r){
        mid=(l+r)/2;
        if(cheak(qqq[mid])){
            r=mid-1;
            ans=qqq[mid];
        }
        else{
            l=mid+1;
        }   
        }
        cout<<ans;
    return 0;
}

by 风中の菜鸡 @ 2021-11-28 17:14:36

@lucky叶 谢谢