P1462-通往奥格瑞玛的道路

小咪咪 2023-06-01 08:55 9阅读 0赞

1 #include <bits/stdc++.h>
      2 #define pb push_back
      3 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
      4 #define INF 1000000003
      5 #define ll long long
      6 
      7 using namespace std;
      8 
      9 const int maxn = 50003;
     10 inline ll read()
     11 {
     12     ll ans = 0;
     13     char ch = getchar(), last = ' ';
     14     while(!isdigit(ch)) last = ch, ch = getchar();
     15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
     16     if(last == '-') ans = -ans;
     17     return ans;
     18 }
     19 inline void write(ll x)
     20 {
     21     if(x < 0) x = -x, putchar('-');
     22     if(x >= 10) write(x / 10);
     23     putchar(x % 10 + '0');
     24 }
     25 struct edge
     26 {
     27     ll to;
     28     ll cost;
     29 };
     30 vector<edge> G[maxn];
     31 
     32 ll V,E,B;
     33 
     34 typedef pair<ll,ll> P;//first 是最短距离，second 是顶点编号 
     35 ll d[maxn];
     36 ll f[maxn];
     37 
     38 bool shortest_path(ll s,ll lim)
     39 {
     40     priority_queue<P,vector<P>,greater<P>> que;
     41     ll ans = -1;
     42     _for(i,1,V+1)
     43         d[i] = INF;
     44     d[s] = 0;
     45     que.push(P{
        0,s});
     46 
     47     while(!que.empty())
     48     {
     49         P p = que.top();que.pop();
     50         ll v = p.second;
     51         if(d[v] < p.first) continue;
     52         _for(i,0,G[v].size())
     53         {
     54             edge e = G[v][i];
     55             if(d[e.to] > d[v] + e.cost && f[e.to] <= lim)
     56             {
     57                 d[e.to] = d[v] + e.cost;
     58                 que.push(P{d[e.to],e.to});
     59             }
     60         }
     61     }
     62     if(d[V]>=B)
     63         return false;
     64     return true;
     65 }
     66 bool C(ll dd)
     67 {
     68     return shortest_path(1,dd);
     69 }
     70 void solve()
     71 {
     72     ll t[maxn];
     73     memcpy(t,f,maxn*sizeof(ll));
     74     sort(t+1,t+V+1);
     75     ll lb = 1,ub = V;
     76     
     77     if(!C(t[ub]))
     78     {
     79         printf("AFK\n");
     80         return ;
     81     }
     82     while(ub - lb > 1)
     83     {
     84         int mid =  lb+(ub-lb)/2;
     85         if(C(t[mid])) ub = mid;
     86         else lb = mid;
     87     }
     88     if(C(t[lb]))
     89         write(t[lb]);
     90     else
     91         write(t[ub]);
     92 }
     93 int main()
     94 {
     95 //    freopen("testdata (1).in","r+",stdin);
     96     
     97     V = read(),E = read(),B = read();
     98     _for(i,1,V+1)
     99     {    f[i] = read();}
    100 //    scanf("%d %d %d",&V,&E,&st);
    101     _for(i,0,E)
    102     {
    103         ll s,t,c;
    104         s = read(),t = read(),c = read();
    105         //  scanf("%d %d %d",&s,&t,&c);
    106         G[s].push_back(edge{t,c});
    107         G[t].push_back(edge{s,c});
    108         
    109     }
    110     
    111     solve();
    112     
    113     //printf("%d ",d[i]);
    114     return 0;
    115 }

转载于:https://www.cnblogs.com/Asurudo/p/11518368.html