PYD1 @ 2020-10-03 12:10:28

by PYD1 @ 2020-10-03 12:10:52

#define INF 0x3f3f3f3f

#include <queue>
#include <cstdio>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

using namespace std;

inline int read(){
    int t = 0,flag = 1;
    register char c = getchar();
    while (c < 48 || c > 57) {if (c == '-') flag = -1;c = getchar();}
    while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = getchar();
    return flag * t;
}//快读 

inline int max(int a,int b) {return a > b ? a : b;}
inline int min(int a,int b) {return a < b ? a : b;}

struct edge{
    int u,v,w,next;
}e[200001];

struct node{
    int i,w;
    node (int i,int w)
        :i(i),w(w) {}
    bool operator < (const node &b) const{
        return this -> w < b.w;
    }
};

int n,m,b,u,v,w,l,r,cnt,fmax,etot,head[20001],f[20001],dis[20001];
bool vis[20001];

priority_queue <node> q;

void addedge(int u,int v,int w){
    e[++etot].u = u,e[etot].v = v,e[etot].w = w,e[etot].next = head[u],head[u] = etot;
}//存图 

bool check(int limit){
    memset(dis,63,sizeof(dis)),memset(vis,0,sizeof(vis)),dis[1] = 0,cnt = 0;
    if (f[1] > limit || f[n] > limit) return 0;
    for (int i = head[1];i;i = e[i].next){
        if (f[e[i].v] <= limit) dis[e[i].v] = min(dis[e[i].v],e[i].w),q.push(node(e[i].v,e[i].w));
    }
    while (!q.empty() && cnt < n){
        node now = q.top();
        q.pop();
        if (vis[now.i]) continue;
        vis[now.i] = 1,++cnt;
        for (int i = head[now.i];i;i = e[i].next){
            if (f[e[i].v] <= limit){
                if (dis[e[i].v] > dis[now.i] + e[i].w) dis[e[i].v] = dis[now.i] + e[i].w,q.push(node(e[i].v,e[i].w));
            }
        }
    }
    if (dis[n] <= b) return 1;
    return 0;
}//堆优化Dijkstra 

int main(){
    n = read(),m = read(),b = read();
    for (int i = 1;i <= n;i++) f[i] = read(),fmax = max(fmax,f[i]);
    for (int i = 1;i <= m;i++) u = read(),v = read(),w = read(),addedge(u,v,w),addedge(v,u,w);//读入+建图 
    l = 1,r = fmax;
    if (!check(fmax)) puts("AFK"),exit(0);
    while (l < r){
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }//二分答案 
    printf("%d\n",l);
    return 0;
}

by PYD1 @ 2020-10-03 12:11:41

各位巨佬提供Hack数据也可以的啊QAQ

by 所有人袛旳 @ 2020-10-03 19:20:43

您看，大佬神贴就是没有人回复