一半re，一半wa，大佬求调（一分不得）

truekun @ 2024-01-29 16:55:55

#include<bits/stdc++.h>
using namespace std;
const int inf=5e4;
int f[inf];
int vis[inf];
priority_queue< pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct node{
    int y,z;
};
int dis[inf];
int n,m,b;
vector <node> E[inf];
bool check(int mid){
    if(f[1]>mid) return false;
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        vis[i]=0;
    }
    //printf("ok\n");
    dis[1]=0;
    q.push({0,1});
    while(!q.empty()){
        int u=q.top().second;

        q.pop();
        if(vis[u]){
            continue;
        }
        //printf("u=%d dis=%d\n",u,dis[u]);
        vis[u]=1;
        for(auto ed:E[u]){
            int v=ed.y,w=ed.z;
            if(dis[v]>dis[u]+w&&f[v]<=mid){
                dis[v]=dis[u]+w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
    //printf("mid=%d %d %d\n",mid,dis[n],b);
    if(dis[n]<b){
        return true;
    }else{
        return false;
    }
}
int main(){

    cin>>n>>m>>b;
    for(int i=1;i<=m;i++){
        cin>>f[i];
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        E[x].push_back((node){y,z});
        E[y].push_back((node){x,z});
    }
    //printf("check=%d\n",check(100));
    //printf("check=%d\n",check(100));
    //return 0;
    int l=1,r=1e9;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    if(l==1||r==1e9){
        cout<<"AFK";
    }else{
        cout<<l;
    }

  return 0;
}

by truekun @ 2024-01-29 16:59:41

求救求救

by truekun @ 2024-01-30 09:35:39

求救

by Doppler @ 2024-01-30 12:21:52

小改了几处：

• 输入fi的时候一共n个点，循环从1到n而不是从1到m
• dijkstra初始化dis的时候5e4不够大，可以改成0x3f3f3f3f
• check最后返回的时候，dis[n]可以等于b（血量不为负就行）

#include<bits/stdc++.h>
using namespace std;
const int inf=5e4 + 5;
int f[inf];
int vis[inf];
priority_queue< pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct node{
    int y,z;
};
int dis[inf];
int n,m,b;
vector <node> E[inf];
bool check(int mid){
    if(f[1]>mid) return false;
    for(int i=1;i<=n;i++){
        dis[i]=0x3f3f3f3f;
        vis[i]=0;
    }
    dis[1] = 0;
    while(!q.empty()) q.pop();
    //printf("ok\n");
    q.push({0,1});
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]){
            continue;
        }
        //printf("u=%d dis=%d\n",u,dis[u]);
        vis[u]=1;
        for(auto ed:E[u]){
            int v=ed.y,w=ed.z;
            if(f[v] > mid) continue;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
    //printf("mid=%d %d %d\n",mid,dis[n],b);
    if(dis[n]<=b){
        return true;
    }else{
        return false;
    }
}
int main(){

    cin>>n>>m>>b;
    for(int i=1;i<=n;i++){
        cin>>f[i];
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        E[x].push_back((node){y,z});
        E[y].push_back((node){x,z});
    }
    //printf("check=%d\n",check(100));
    //printf("check=%d\n",check(100));
    //return 0;
    int l=max(f[1], f[n]),r=1e9, ans = 0x3f3f3f3f;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans = mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    if(ans == 0x3f3f3f3f){
        cout<<"AFK";
    }else{
        cout<<ans;
    }

  return 0;
}

by truekun @ 2024-01-30 16:38:13

@Doppler 膜拜dalao

by truekun @ 2024-01-30 16:39:05

@truekun 已经AC（4年级小学生诚心感谢）