洛咕题解 P1462 通往奥格瑞玛的道路[二分答案,最短路]

  • A+
所属分类:代码笔记 信息技术

这道题要求最大收费点的最小值,明显是二分答案

二分check(maxf)函数目标:判断能否在 最大收费点小于maxf 的条件下,走到终点

能则缩小maxf, 否则只能是更大的maxf

具体实现: dijkstra松弛的时候加个判断 点权要小于maxf 就行了

  1. #include<cstdio>
  2. #include<queue>
  3. #define re register
  4. #define int long long
  5. //十年竞赛一场空
  6. //没开longlong见祖宗
  7. //总有你想不到的地方炸了int
  8. using namespace std;
  9. inline int read()
  10. {
  11.     int s=0,b=1;
  12.     char ch;
  13.     do{
  14.         ch=getchar();
  15.         if(ch=='-') b=-1;
  16.     }while(ch<'0' || ch>'9');
  17.     while(ch>='0' && ch<='9')
  18.     {
  19.         s=s*10+ch-'0';
  20.         ch=getchar();
  21.     }
  22.     return b*s;
  23. }//快读是不可能出锅的
  24. struct edge{
  25.     int t,w,next;
  26. }e[510000];
  27. int head[110000],cnt=0,n,m,b,f[110000];
  28. //十年竞赛一场空
  29. //数组开小见祖宗
  30. //别吝啬空间!
  31. //总有你想不到的地方炸了你的数组
  32. inline void add(int f,int t,int w)
  33. {
  34.     //printf("%lld\n",cnt);
  35.     //十年竞赛一场空
  36.     //不删DeBug见祖宗
  37.     ++cnt;
  38.     e[cnt].t=t;
  39.     e[cnt].w=w;
  40.     e[cnt].next=head[f];
  41.     head[f]=cnt;
  42. }
  43. struct node{
  44.     int dis,num;
  45.     bool operator < (const node & t)const
  46.         {
  47.             return dis>t.dis;
  48.         }
  49. };
  50. priority_queue<node> q;
  51. int dis[11000];
  52. bool dijkstra(int maxf) //返回路径上每个点的权值小于maxf时, 能否走到终点
  53. {
  54.     //标准dijkstra, 只是在松弛时加入了节点的权值不能超过maxf的条件
  55.     //这样就可以保证求出 经过的节点的权值都不超过maxf 条件下的最短路
  56.     if(f[1]>maxf) return false//注意题目说起点也要算花费
  57.     for(re int i=1;i<=n;i++) dis[i]=2147483647;
  58.     node x;
  59.     x.num=1;
  60.     x.dis=0;
  61.     dis[1]=0;
  62.     q.push(x);
  63.     while(!q.empty())
  64.     {
  65.         x=q.top();
  66.         q.pop();
  67.         int u=x.num;
  68.         if(x.dis!=dis[u]) continue;
  69.         for(re int i=head[u];i;i=e[i].next)
  70.         {
  71.             int v=e[i].t,w=e[i].w;
  72.             if(dis[u]+w<dis[v] && f[v]<=maxf)
  73.             {
  74.                 dis[v]=dis[u]+w;
  75.                 node x1;
  76.                 x1.num=v;
  77.                 x1.dis=dis[v];
  78.                 q.push(x1);
  79.             }
  80.         }
  81.     }
  82.     if(dis[n]>=b) return false;
  83.     //如果求出来1到n的最短路长度大于血量
  84.     //则不能做到使 路径上每个点的权值都不超过maxf
  85.     else return true;
  86. }
  87. signed main()
  88. {
  89.     n=read();
  90.     m=read();
  91.     b=read();
  92.     int x,y,z;
  93.     int l=2147483647,r=0;
  94.     for(re int i=1;i<=n;++i)
  95.     {
  96.         f[i]=read();
  97.         if(f[i]<l) l=f[i];
  98.         if(f[i]>r) r=f[i];
  99.     }//预处理出二分的区间:最小点权~最大点权
  100.     for(re int i=1;i<=m;++i)
  101.     {
  102.         x=read();
  103.         y=read();
  104.         z=read();
  105.         add(x,y,z);
  106.         add(y,x,z);
  107.         //注意是无向图
  108.     }
  109.     if(!dijkstra(2147483647)){
  110.         printf("AFK\n");
  111.         //无限制的情况下,如果不能从起点走到终点,肯定输出 啊♂FUCK
  112.         return 0;
  113.     }
  114.     //下面就是标准二分
  115.     while(l<r)
  116.     {
  117.         int mid=(l+r)/2;
  118.         if(!dijkstra(mid)) l=mid+1;
  119.         else r=mid;
  120.     }
  121.     printf("%lld\n",l);
  122.     return 0;
  123. }
xcc

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: