80pts WAon #5 #8 #11 #13求条

_xdd_ @ 2024-08-24 10:31:10

#include<bits/stdc++.h>
#define maxn 10005
#define maxm 50005
#define maxb 1000000005
#define int long long
using namespace std;
int n,m,b,f[maxn],head[maxn],dis[maxn],cnt;
bool vis[maxn];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
struct node{
    int next,to,w;
}edge[maxm<<1];
void addedge(int u,int v,int w){
    edge[cnt++].next=head[u];
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}
bool check(int x){
    if(x<f[1]){return 0;}
    for(int i=1;i<=n;i++){
        dis[i]=1e9;
        vis[i]=0;
    }
    dis[1]=0;
    q.push(make_pair(0,1));
    while(q.size()){
        int u=q.top().second;
        q.pop();
        if(!vis[u]){
            vis[u]=1;
            for(int i=head[u];i;i=edge[i].next){
                int v=edge[i].to;
                if(f[v]<=x && dis[v]>dis[u]+edge[i].w){
                    dis[v]=dis[u]+edge[i].w;
                    if(!vis[v]){
                        q.push(make_pair(dis[v],v));
                    }
                }
            }
        }
    }
    return dis[n]<=b;
}
signed main(){
    cin >> n >> m >> b;
    for(int i=1;i<=n;i++){
        cin >> f[i];
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        addedge(a,b,c);
        addedge(b,a,c);
    }
    if(!check(maxb)){
        cout << "AFK";
        return 0;
    }
    int l=1,r=maxb;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    cout << l;
}

by liuzhuoran141516 @ 2024-08-24 10:41:25

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue> 
#include<cstring>
#define il inline
#define rg register
#define N 10005
#define M 100005
#define MAXN 1000000005//最大收费（二分用 
using namespace std;
int f[N];//每个城市的收费额度
bool ed[N];//求最短路使用
int dis[N];//同上
int head[N];//前向星 
priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;
int n,m,b;
int t;
struct edge{
    int to,next,len;
}e[M];
il void add(int x,int y,int z){
    e[++t].len=z;
    e[t].to=y;
    e[t].next=head[x];
    head[x]=t;
}
il int read(){
    int sum=0;char a=getchar();
    while(a<'0'||a>'9')a=getchar();
    while(a>='0'&&a<='9'){
        sum=(sum<<3)+(sum<<1)+a-'0';
        a=getchar();
    }
    return sum;
}
il bool work(int x){//对于每个最大收费都确定是否可以到达 
   if(x<f[1])return 0;//起点都过不了走个p 
    for(int i=1;i<=n;i++){
        dis[i]=1e9;//初始化为极大值 
    }
    memset(ed,0,sizeof(ed));
    dis[1]=0;
    que.push(make_pair(0,1));
    int s1,s2;
    while(que.size()){
        s1=que.top().second;que.pop();
        if(ed[s1])continue;
        ed[s1]=1;
        s2=head[s1];
        while(s2){//只有收费小于x的才能使用，大于x的一律视为没有 
            if(f[e[s2].to]<=x&&ed[e[s2].to]==0&&dis[s1]+e[s2].len<dis[e[s2].to])
            {dis[e[s2].to]=dis[s1]+e[s2].len;
            que.push(make_pair(dis[e[s2].to],e[s2].to));}//入堆准备下一轮操作 
            s2=e[s2].next;//去下一条边 
        }
    }
    if(dis[n]<b){
        return 1;
    }
    return 0;
}
int main(){
    n=read();m=read();b=read();
    for(rg int i=1;i<=n;i++)
    f[i]=read();//储存费用
    int a1,a2,a3;
    for(rg int i=1;i<=m;i++){
        a1=read();a2=read();a3=read();
        add(a1,a2,a3);
        add(a2,a1,a3);
    }
    if(work(MAXN)==0){
        cout<<"AFK"<<endl;
        return 0;//如果所有都开通任然不满足条件，剩下的肯定也不会满足 
    } 
    int l=1,r=MAXN,mid=(l+r)>>1;//准备开始二分
    int c;
    while(l<=r){
        c=work(mid);
        if(c){//如果可以的话 
            r=mid-1;
            mid=(l+r)>>1;
         }
        else{
            l=mid+1;
            mid=(l+r)>>1;
         }
     }
     cout<<l<<endl;
}

by _xdd_ @ 2024-08-24 15:43:05

@liuzhuoran141516 拿个题解代码装模做样的来求助好玩吗