首页技术正文

洛谷 P1462 通往奥格瑞玛的道路（spfa+二分搜索）（4boy）

程序员振州技术 2022年11月20日

0 收藏 726 点赞 3,886 浏览 1458 个字

原题:http://www.luogu.org/problem/show?pid=1462#sub

4boy:

大意:给出n个城市，有m条路，每经过一个城市都要交钱，每经过一条道路都要扣HP，有HP上限；要从1走到n，

求在HP没扣完的情况下，从1到n经过城市的最大花费的最小值。

思路:用二分搜索cost的值的最小值，用spfa搜索从1到n所需的最少HP，在spfa中判断cost[i]与x详见代码注释；

 #include<iostream>
 #include<cstring>
 #include<queue>
 #define maxn 100000
 #define INF 0x3f3f3f3f
 #define ll long long
 using namespace std;
 queue<int> q;
 int n,m;
 int edgenum=,link[maxn],v[maxn];
 ll b,ans=-,max_c=-,cost[maxn],dis[maxn];
 struct EDGE   //边表优化
 {
      int v,next;
      ll val;
      EDGE(){next=;}
 }edge[maxn];
 void add(int a,int b,int x)
 {
      edgenum++;
      edge[edgenum].v=b;
      edge[edgenum].val=x;
      edge[edgenum].next=link[a];
      link[a]=edgenum;
 }
 void init()
 {
      cin>>n>>m>>b;
      for(int i=;i<=n;i++)
      {
         cin>>cost[i];
         max_c=max(max_c,cost[i]);
      }
      int x,y,l;
      for(int i=;i<=m;i++)
      {
         cin>>x>>y>>l;
         add(x,y,l);
         add(y,x,l);
      }
 }
 bool spfa(ll x)
 {
      memset(dis,INF,sizeof(dis));
      memset(v,,sizeof(v));
      dis[]=;
      v[]=;
      q.push();
      while(!q.empty())
      {
         int temp=q.front();
         q.pop();
         v[temp]=;
         for(int i=link[temp];i!=;i=edge[i].next)
         {
            if(cost[edge[i].v]>x) continue;       //此城市的cost>期望最小值x，则跳过
            if(dis[edge[i].v]>dis[temp]+edge[i].val)
            {
               dis[edge[i].v]=dis[temp]+edge[i].val;
               if(!v[edge[i].v])
               {
                  q.push(edge[i].v);
                  v[edge[i].v]=;
               }
            }
         }
      }
      if(dis[n]>b || dis[n]==(ll)INF) return false;  //最短路的HP>上限 || 不通 则false
      return true;
 }
 void work()
 {
      ll mid;
      ll l=,r=max_c;
      while(l<=r)
      {
         mid=(r+l)>>;
         if(spfa(mid)==true) //已mid为值的cost可通，记录答案并搜索区间左移
         {
            r=mid-;
            ans=mid;
         }
         else    //不通，搜索区间右移
         {
            l=mid+;
         }
      }
     if(ans==-) cout<<"AFK";
     else cout<<ans;
 }
 void pt()
 {
      //if(spfa(10)) cout<<"fuck you";
 }
 int main()
 {
     init();
     work();
     //pt();
     //system("pause");
     return ;
 }