题目：

二分答案。

为什么djkstra不行，spfa可以？

其实是自己把priority_queue写成queue了……

priority_queue竟然是从大到小排的？！

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int N=1e5+5,M=5e5+5;int n,m,head[N],xnt;ll b,v[N],l,r,ans=-1,dis[N];bool vis[N];struct Edge{    int next,to;ll w,c;    Edge(int n=0,int t=0,ll w=0,ll c=0):next(n),to(t),w(w),c(c) {}}edge[M<<1];struct Node{    int bh;ll c;    Node(int b=0,ll c=0):bh(b),c(c) {}    bool operator <(const Node &a)const    {
    return c
         
           q;    dis[1]=0;q.push(Node(1,0));    while(q.size())    {        int k=q.front().bh;q.pop();        while(q.size()&&vis[k])k=q.front().bh,q.pop();        if(vis[k])break;vis[k]=1;        for(int i=head[k],v;i;i=edge[i].next)        {//            if(edge[i].c<=mid)printf("1");//            if(dis[v=edge[i].to]>dis[k]+edge[i].w)printf("2");//            if(dis[k]+edge[i].w<=b)printf("3");printf("v=%d\n",v);            if(edge[i].c<=mid&&dis[v=edge[i].to]>dis[k]+edge[i].w&&dis[k]+edge[i].w<=b)            {dis[v]=dis[k]+edge[i].w;q.push(Node(v,dis[v]));if(v==n)return true;}        }    }    return false;}bool spfa(ll mid){    memset(dis,11,sizeof dis);    memset(vis,0,sizeof vis);    queue
          
            q; q.push(1);dis[1]=0;vis[1]=1; while(q.size()) { int k=q.front();q.pop();vis[k]=0; for(int i=head[k],v;i;i=edge[i].next) if(edge[i].c<=mid&&dis[v=edge[i].to]>dis[k]+edge[i].w&&dis[k]+edge[i].w<=b) { dis[v]=dis[k]+edge[i].w; if(!vis[v])vis[v]=1,q.push(v); if(v==n)return true; } } return false;}int main(){// freopen("洛谷1462#8.in","r",stdin); scanf("%d%d%lld",&n,&m,&b);int x,y;ll z; for(int i=1;i<=n;i++)scanf("%lld",&v[i]),r=max(r,v[i]); for(int i=1;i<=m;i++) { scanf("%d%d%lld",&x,&y,&z); add(x,y,z); }// printf("l=%lld r=%lld\n",l,r); while(l<=r) { ll mid=((l+r)>>1); if(spfa(mid))ans=mid,r=mid-1; else l=mid+1; } if(ans==-1)printf("AFK"); else printf("%lld",ans); return 0;}