luogu-P1462 通往奥格瑞玛的道路 && ybt-修建道路【最短路+二分】

P1462 通往奥格瑞玛的道路 link

思路：
首先，看见这个问题，就应该想到二分。

所有类似于“求解所有的最大值中的最小值”的问题，都应该先想一想用二分答案的方法来写。

为什么呢？因为二分答案就是用来求解这种问题的，它通过猜测目前的答案+验证目前答案是否成立来求解，这种“假设已经知道答案”的方法比用题目信息求解答案的方法要优秀很多，而且复杂度也仅仅是加了一个log。

但是还要注意一点，除了这种经典问法以外，还要通过答案是否具有单调性来判断是否可以使用二分答案的方法

不具有单调性的问题是不可以使用这种方法的！
回到本题，我们猜测可以使用二分答案后，再验证：由于 “我们假设需要的钱”越多，能走的点也就越多，可以走到终点的可能性也就越大，所以，这题是完全可以通过二分答案来写的。

然后，我们发现这里有两个变量：血量和费用。至于费用，我们已经用二分答案解决了，现在只需要解决血量的问题。 我们在上面分析了，损失血量是和边绑定在一起的，所有可以把损失血量看做每条边的长度，进而就到了这题的中心——单源最短路。

#include
using namespace std;
#define ong long long
const int N=10010;
const int M=100010;
const ong inf=LLONG_MAX/3;  //小心爆long long
int n,m,b,u,v;
int l,r,mid;
ong wi;  //爆int了
struct node{
	int a;
	ong dis;
};
bool operator < (node x,node y){
	return x.dis>y.dis; 
} priority_queue<node> q;
int top,g[N],f[N];
ong dis[N];
bool vis[N];
struct edge{
	int adj,nex;
	ong w;
}e[M];
void add(int x,int y,ong wor){
	e[++top]=(edge){y,g[x],wor}; 
	g[x]=top;
} void Dijkstra(int maxn){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
		vis[i]=0;
	} dis[1]=0;
	while(!q.empty()) q.pop();
	q.push((node){1,dis[1]});
	while(!q.empty()){
		node now=q.top(); q.pop();
		int x=now.a;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=g[x];i;i=e[i].nex){
			int p=e[i].adj;
			if(f[p]>maxn) continue;
			if(dis[x]+e[i].w<dis[p]){
				dis[p]=dis[x]+e[i].w;
				q.push((node){p,dis[p]});
			}
		}
	}
} int main(){
	scanf("%d%d%d",&n,&m,&b);
	for(int i=1;i<=n;i++){
		scanf("%d",f+i);
		r=max(r,f[i]);
	} l=max(f[1],f[n]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&wi);
		add(u,v,wi);
		add(v,u,wi);
	} while(l<r){
		mid=(l+r)>>1;
		Dijkstra(mid);
		if(dis[n]>b)
			l=mid+1;  //怕死循环
		else r=mid;
	} Dijkstra(l);
	if(dis[n]>b) printf("AFK\n");
	else printf("%d\n",l);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

F. 2.修建道路 link

思路：
这题的思路和上题有异曲同工之妙。
都是最值的最值，考虑用二分。
关心另一个变量k与边有关系，那么可以采用最短路的方法。
我们逆向思维转换一下，每次二分出自己建设道路的最大代价val，那么超过凡是超过val的边，我们将边权设为1,表示需要政府修建此路，反则为0。那对于最后的dis[n]就表示从1~n的最短路上，需要政府修建的最小路数。最后我们只需与k比较作为二分的条件。

#include 

using namespace std;

const int N = 2e4 + 10;

int n, p, k, dis[N], ans;
bool vis[N];

vector <pair<int, int> > G[N];

bool dij(int val)
{
	priority_queue<pair<int, int> > Q;
	memset(dis, 0x4f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	dis[1] = 0;
	Q.push(make_pair(0, 1));
	while(!Q.empty())
	{
		pair<int, int> tx = Q.top();
		Q.pop();
		if(vis[tx.second]) continue;
		int u = tx.second;
		vis[u] = 1;
		for(int i = 0; i < G[u].size(); i++)
		{
			int v = G[u][i].first;
			if(dis[v] > dis[u] + (G[u][i].second > val))
			{
				dis[v] = dis[u] + (G[u][i].second > val);
				Q.push(make_pair(-dis[v], v));
			}
		}
 	}
 	return (dis[n] <= k);
}

int main()
{
	scanf("%d%d%d", &n, &p, &k);
	for(int i = 1; i <= p; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].push_back(make_pair(v, w));
		G[v].push_back(make_pair(u, w));
	}
	int l = 0, r = 2147483647, mid;
	if(!dij(r)) {printf("-1\n"); return 0;}
	while(l <= r)
	{
		mid = (l + r) / 2;
		if(dij(mid))
		{
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	printf("%d\n", ans);
 	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64