【洛谷P1462】【二分+堆优化dij】

题目描述

在艾泽拉斯，有n个城市。编号为1,2,3,...,n。

城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设1为暴风城，n为奥格瑞玛，而他的血量最多为b，出发时他的血量是满的。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

题目分析

题目说了那么多，其实就是让求在角色不死亡的情况下移动过程遇到的F[i]的最大值的最小值..【看到最大值的最小值就应该立马想到二分啊..然而蒟蒻终究是蒟蒻..没想到二分..而是无脑堆优化的使用dij..结果TLE到怀疑人生，看到别人的题解之后才想到用二分..orz..】

题意这样就很明白了二分是一定要用的这种问法基本十个有九个是要用二分

那么我们要二分什么呢血量还是金钱呢

因为要求的是收费所以就二分金钱好了////

二分的条件就是以当前值为最大值，不走大于二分值的点，然后用堆优化的dij判断是否连通就行了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 using namespace std;
 6 const int maxn1=10000;
 7 const int maxn2=50000;
 8 const int maxn3=1000000005;
 9 struct pot{
10     int id;
11     int rest;
12      bool operator <(const struct pot&AA)const{
13         return rest < AA.rest;
14     }
15 };
16 struct edge{
17     int next;
18     int to;
19     int len;
20 }EDGE[maxn2*2+5];
21 int dist[maxn1+5],head[maxn1+5],dist1[maxn1+5];
22 int n,m,b;
23 int edge_cnt=0;
24 priority_queue<struct pot>pq;
25 void add(int x,int y,int z)
26 {
27     EDGE[edge_cnt].to=y;
28     EDGE[edge_cnt].next=head[x];
29     EDGE[edge_cnt].len=z;
30     head[x]=edge_cnt++;
31 }
32 int mmin=-1;
33 bool dij(int x)
34 {
35     memset(dist1,0,sizeof(dist1));
36     while(!pq.empty())
37     {
38         pq.pop();
39     }
40     pq.push((struct pot){1,b});
41     while(!pq.empty())
42     {
43         struct pot aa=pq.top();pq.pop();
44         if(aa.rest<dist1[aa.id])continue;
45         for(int i = head[aa.id]; i != -1 ; i=EDGE[i].next)
46         {
47             int v=EDGE[i].to;
48             if(dist[v]<=x&&aa.rest-EDGE[i].len>0)
49             {
50                 if(v==n){
51                 return true;
52             }
53                 if(dist1[v]<aa.rest-EDGE[i].len)
54                 {
55                     dist1[v]=aa.rest-EDGE[i].len;
56                     pq.push((struct pot){v,aa.rest-EDGE[i].len});
57                 }
58             }
59         }
60     }
61     return false;
62 }
63 int main()
64 {
65     scanf("%d%d%d",&n,&m,&b);
66     int r=0;    
67     for(int i = 1 ; i <= n ; i++)
68     {
69         scanf("%d",&dist[i]);
70         r=max(r,dist[i]);
71     }
72     memset(head,-1,sizeof(head));
73     while(m--)
74     {
75         int q,w,e;
76         scanf("%d%d%d",&q,&w,&e);
77         add(q,w,e);
78         add(w,q,e);
79     }
80     int l=max(dist[1],dist[n]);
81     bool flag=false;
82     while(l<=r)
83     {
84         int mid=(l+r)/2;
85         if(dij(mid)){
86             r=mid-1;
87             flag=true;
88         }
89         else
90         {
91             l=mid+1;
92          } 
93     }
94     if(!flag)
95     printf("AFK
");
96     else
97     cout << l<< endl;
98     return 0;
99 }

View Code