蒟蒻求助

RT

评测记录

代码

#include<iostream>
#include<cstdio>
#include<climits>
#include<queue>
using namespace std;

const int MAXN = 10005,MAXM = 100010,INF = INT_MAX;
int n,m,b,x,y,z,head[MAXN],cnt,crtm,mny[MAXN],dis[MAXN],le = INF,ri,mid,id,d,beu;
bool vis[MAXN],yes;

struct Edge {
    int to;
    int w;
    int nxt;
} l[MAXM];
struct Node {
    int id;
    int dis;
};

priority_queue<Node> q;
bool operator < (const Node &a,const Node &b){
    return (a.dis > b.dis);
}

void add(int x,int y,int z){
    cnt++;
    l[cnt].to = y;
    l[cnt].w = z;
    l[cnt].nxt = head[x];
    head[x] = cnt;
}
void init(){
    for(int i=1;i<=n;i++){
        dis[i] = INF;
        vis[i] = false;
    }
}
bool dijk(){
    init();
    dis[1] = 0;
    q.push(Node{1,0});
    Node crt;
    while(!q.empty()){
        crt = q.top();
        q.pop();
        id = crt.id;
        if(vis[id]){
            continue;
        }
        //如果当前城市的收费大于要求的收费那就不走 
        if(mny[id] > mid){
            continue;
        }
        vis[id] = true;
        d = dis[id] = crt.dis;
        for(int i=head[id];i;i=l[i].nxt){
            beu = l[i].to;
            if(!vis[beu] && dis[beu] > d + l[i].w){
                q.push(Node{beu,d + l[i].w});
            }
        }
    }
    if(dis[n] < b){
        yes = true;
        return true;
    }else{
        return false;
    }
}

int main(void){
    //得到点的数量、边的数量和歪嘴哦的血量
    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",&crtm);
        mny[i] = crtm;
        ri = max(crtm,ri);
        le = min(crtm,le);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z); 
    } 
    while(le < ri){
        mid = (le + ri) / 2;
        if(dijk()){
            ri = mid;
        }else{
            le = mid + 1;
        }
    }
    mid = le;
    dijk();
    if(yes){
        printf("%d",le);
    }else{
        printf("AFK");
    }
    return 0;
}