90tps求调玄关QAQ WA#8#13

P1462 通往奥格瑞玛的道路

Rt__ @ 2024-09-24 11:30:25

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N=5000010;

int n,m;
ll cw[N],b;
int h[N],idx,e[N],ne[N];
ll w[N];
ll d[N];
void add(int a,int b,ll c){
    ne[idx]=h[a],e[idx]=b,w[idx]=c,h[a]=idx++;
    return ;
}
struct node{
    int i;
    ll w;
    bool operator<(const node a)const{
        return w>a.w;
    }
}maxc[N];
bool cmp(node a,node b){
    return a.w<b.w;
}
bool dij(int x){
    if(cw[1]>cw[x])return false;
    priority_queue<node>q;
    memset(d,0x3f,sizeof d);
    d[1]=0;
    q.push({1,0});
    while(q.size()){
        node now=q.top();
        q.pop();
        int u=now.i,dist=now.w;
        for(int i=h[u];i!=-1;i=ne[i]){
            int j=e[i];
            if(cw[j]>cw[x])continue;
            if(d[j]>dist+w[i]){
                d[j]=dist+w[i];
                q.push({j,d[j]});
            }
        }
    }
    ll ans=d[x];
    if(ans>b)return false;
    memset(d,0x3f,sizeof d);
    q.push({x,0});
    d[x]=0;
    while(q.size()){
        node now=q.top();
        q.pop();
        int u=now.i,dist=now.w;
        for(int i=h[u];i!=-1;i=ne[i]){
            int j=e[i];
            if(cw[j]>cw[x])continue;
            if(d[j]>dist+w[i]){
                d[j]=dist+w[i];
                q.push({j,d[j]});
            }
        }
    }
    if(ans+d[n]>b)return false;
    return true;
}
signed main(){
    memset(h,-1,sizeof h);
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++){
        cin>>cw[i];
        maxc[i]={i,cw[i]};
    }
    sort(maxc+1,maxc+1+n,cmp);
    for(int i=1;i<=m;i++){
        int a,b;
        ll c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    /* int yy=10;
    while(yy--){
    int xx;
    cin>>xx;
    cout<<dij(xx);
    cout<<endl;
    }*/
    for(int i=n;i>=1;i--){
        if(!dij(maxc[i].i)){
            cout<<"AFK";
            return 0;
        }
        if(maxc[i].w!=maxc[i-1].w)break;
    }

    int l=0,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        bool c=dij(maxc[mid].i);
        if(c){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<maxc[l].w;
    return 0;
}

救救孩子吧


|