P1462 通往奥格瑞玛的道路

//https://www.luogu.com.cn/problem/P1462?contestId=96625
#include<bits/stdc++.h>
using namespace std;

struct Node
{
   long long v;//临接点
   long long w;//边权
   friend bool operator < (const Node &n1 , const Node &n2)
   {
       return n1.w > n2.w;
   }
};
//bool operator < (Node lhs , Node rhs)
//{
//    return lhs.w > rhs.w;
//}

#define maxn 10010

long long n,m;
long long b;
long long f[maxn];//点权值
vector<Node> G[maxn];

long long dist[maxn];
bool visited[maxn];
priority_queue <Node> h;
bool dijsktra(long long x)//此时的限制点权为x
{
   if(f[1]>x||f[n]>x) return false;//起点终点超过最大点权
   fill(dist,dist+maxn,LONG_LONG_MAX);
   fill(visited,visited+maxn,false);
   //核心：如果此时的点权超过最大值则完全设置为访问
   for(int i=1;i<=n;i++)
   {
       if(f[i]>x)
           visited[i] = true;
   }
   dist[1]=0;
   h.push(Node{1,0});
   while(h.empty()==false)
   {
       long long midnode = h.top().v;
       h.pop();
       if(visited[midnode]==true)
           continue;
       visited[midnode]=true;
       for(int j=0;j<G[midnode].size();j++)
       {
           long long v=G[midnode][j].v;
           long long weight=G[midnode][j].w;
               if (dist[v] > dist[midnode] + weight)
               {
                   dist[v] = dist[midnode] + weight;
                   h.push(Node{v, dist[v]});
               }
       }
   }
   if(dist[n]<b)
       return true;
   else
       return false;
}

int main()
{
   long long maxx = -1 ;//maxx记录的是最大费用
   scanf("%lld%lld%lld",&n,&m,&b);
   for(int i=1;i<=n;i++)
   {
       scanf("%lld",&f[i]);
       if(f[i]>maxx)
           maxx = f[i];
   }

   //存储图
   long long t1,t2,tc;
   for(int i=1;i<=m;i++)
   {
       scanf("%lld%lld%lld",&t1,&t2,&tc);
       if(t1 == t2) continue;//题中说明：可能有两条边连接着相同的城市。
       G[t1].push_back(Node{t2,tc});
       G[t2].push_back(Node{t1,tc});
   }

   //二分点权
   long long l = 1;//最小点权
   long long r =maxx;//最大点权
   long long mid;
   long long ans = -1;
   while(l<=r)
   {
       mid = (l+r)/2;//限制最大点权
       if(dijsktra(mid))
       {
           //如果此次限制可以走通继续二分
           ans = mid ;
           r   = mid -1;
       }
       else
       {
           l = mid + 1;
       }
   }

   if(ans == -1)
   {
       //走不通
       printf("AFK");
   }
   else
   {
       printf("%lld",l);
   }
   return 0;
}