求助40pts TLE#2#5

44_FeiDing @ 2023-08-24 19:18:19

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct edge{
    int v,w;
};
struct point{
    int id,d;
    bool operator <(point a) const{
        return d<a.d;
    }
};
int n,m,b,l=0x7fffffff,r,ans;
int f[10002],dis[10002];
bool vis[10002];
vector<edge> g[10002];
priority_queue<point> q;
void dij(int);
int main(){
    cin>>n>>m>>b;
    for(int i=1;i<=n;++i){
        cin>>f[i];
        r=max(r,f[i]+1);
        l=min(l,f[i]+1);
    }
    for(int i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back((edge){v,w});
        g[v].push_back((edge){u,w});
    }
    while(r-l>1){
        int mid=(r+l)/2;
        dij(mid);
        if(dis[n]<=b){
            r=mid;
        }
        else{
            l=mid;
        }
    }
    dij(r);
    if(dis[n]<=b)
        cout<<r;
    else
        cout<<"AFK";
}
void dij(int maxx){
    memset(vis,0,sizeof(vis));
    memset(dis,0x7f,sizeof(dis));
    while(!q.empty())
        q.pop();
    q.push((point){1,0});
    dis[1]=0;
    while(!q.empty()){
        int u=q.top().id;
        q.pop();
//      if(!vis[u])
//          continue;
//      vis[u]=0;
        for(int i=0;i<g[u].size();++i){
            int v=g[u][i].v;
            int w=g[u][i].w;
            if(f[v]>maxx)
                continue;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push((point){v,dis[v]});
//              vis[v]=1;
            }
        }
    }
}

by 44_FeiDing @ 2023-08-24 19:34:47

memset(vis,0,sizeof(vis));改成memset(vis,1,sizeof(vis));还是一样。

by 44_FeiDing @ 2023-08-24 19:52:47

把q.push((point){v,dis[v]});改成q.push((point){v,-dis[v]});80分了。

by 44_FeiDing @ 2023-08-25 07:47:54

@dltdltdlt record

by 44_FeiDing @ 2023-08-25 08:10:38

@dltdltdlt https://www.luogu.com.cn/record/122634520

by 44_FeiDing @ 2023-08-25 08:15:04

@dltdltdlt

#include<iostream>
#include<queue>
#include<cstring>
#define int long long
using namespace std;
struct edge{
    int v,w;
};
struct point{
    int id,d;
    bool operator <(point a) const{
        return d>a.d;
    }
};
int n,m,b,l=1e18,r,ans;
int f[100002],dis[100002];
bool vis[100002];
vector<edge> g[100002];
priority_queue<point> q;
void dij(int);
signed main(){
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++){
        cin>>f[i];
        r=max(r,f[i]);
    }
    l=max(f[1],f[n]);
    for(int i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back((edge){v,w});
        g[v].push_back((edge){u,w});
    }
    while(r-l>1){
        int mid=(r+l)/2;
        dij(mid);
        if(dis[n]<=b){
            r=mid;
        }
        else{
            l=mid;
        }
    }
    dij(l);
//    for(int i=1;i<=n;++i)
//      cout<<dis[i]<<' ';
//    cout<<endl;
    if(dis[n]<=b)
        cout<<l;
    else
        cout<<"AFK";
}
void dij(int maxx){
    for(int i=1;i<=n;i++){
        dis[i]=1e18;
        vis[i]=0;
    }
    while(!q.empty())
        q.pop();
    q.push((point){1,0});
    dis[1]=0;
    while(!q.empty()){
        int u=q.top().id;
        q.pop();
//        if(vis[u])
//            continue;
//        vis[u]=1;
        for(int i=0;i<g[u].size();++i){
            int v=g[u][i].v;
            int w=g[u][i].w;
            if(f[v]>maxx)
                continue;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push((point){v,dis[v]});
            }
        }
    }
}