0分求助，悬赏关注，谢谢

lcbridge @ 2023-04-01 20:31:14

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100000+5;
const int maxm=200000+5;
int n,m,s,dis[maxn],f[maxn],b,maxx;
struct edge{
    int to,w;
};
vector <edge> g[maxm];
priority_queue <pair<int,int> > q;
bool vis[maxn]; 
bool dij(int k){
    if(k<f[1])return false;
    for(int i=1;i<=n;i++)dis[i]=0x7ffffffff;
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=0;i<g[x].size();i++){
            int to=g[x][i].to;
            if(f[to]>k)continue;
            if(dis[to]>dis[x]+g[x][i].w){
                dis[to]=dis[x]+g[x][i].w;
                q.push(make_pair(-dis[to],to));
            }
        } 
    }
    return dis[n]>=b;
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&b);
    for(int i=1;i<=n;i++){
        scanf("%lld",&f[i]);
        maxx=max(maxx,f[i]);
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    int l=0,r=maxx+1,mid,ans=-1;
    while(l<=r){
        mid=(l+r)>>1;
        if(dij(mid)){
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    if(ans==-1)printf("AFK");
    else printf("%lld",ans);
    return 0;
}   

by Istruggle @ 2023-08-02 13:02:06

借个帖

我也是这么写的，开O2能过几个，帮我也看一下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,b,f[100005],cnt=0,head[100005],r,l;
ll dis[100005];
ll vis[100005];
struct edge
{
    ll v,w,next;
}e[500005];
void addedge(ll u,ll v,ll w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
struct node{
    ll u,d;
    bool operator <(const node&rhs) const{
        return d>rhs.d;
    }
};
bool dij(ll temp){
    if(f[1]>temp) return false;
    memset(vis,0,sizeof(vis));
    for(ll i = 1;i<=n;i++) dis[i]=0x3f;
    priority_queue<node> q;
    q.push((node){1,0});
    dis[1]=0;
    while(!q.empty())
    {
        node fr=q.top(); q.pop();
        ll u = fr.u;
        ll d= fr.d;
        if(vis[u]) continue;
        vis[u]=1;
        for(ll i = head[u];i;i=e[i].next){
            ll y=e[i].v;
            if(e[i].w>temp) continue;
            if(dis[y]>dis[u]+e[i].w){
                dis[y]=dis[u]+e[i].w;
                if(!vis[y])
                {
                    q.push((node){y,dis[y]});
                }
            }
        }
    }
    if(dis[n]<b) return true;
    else return false;
}
int main()
{
    scanf("%d%d%d",&n,&m,&b);
    for(ll i= 1;i<=n;i++)
    scanf("%d",&f[i]),r=max(r,f[i]);
    for(ll i = 1;i<=m;i++){
        ll a,b1,c;
        scanf("%d%d%d",&a,&b1,&c);
        if(a==b1) continue;
        addedge(a,b1,c);
        addedge(b1,a,c);
    } 
    int ans=-1;
    l=max(f[1],f[n]); 
    while(l<=r){
        ll mid=(l+r)>>1;
        if(dij(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    if(ans==-1) {
        cout<<"AFK";return 0;
    }
    printf("%d",ans);
    return 0;
}