Catalog
  1. 1. 核心思路
  2. 2. check函数
  3. 3. 注意事项
  4. 4. 代码
题解 P1951 【收费站_NOI导刊2009提高(2)】

查看原题请戳这里

核心思路

题目让求最大费用的最小值,很显然这道题可以二分,于是我们可以二分花费的最大值。

check函数

那么,我们该怎么写check函数呢?

我们可以删去费用大于mid的点以及与其相连的边,然后在剩余的点和边组成的图上跑一遍最短路求出从u到v需要消耗的最小的汽油,如果消耗汽油最小值不大于s,那么返回true,否则返回false。

注意事项

  1. 在二分时一定要判断到起点的花费是否大于mid
  2. r的初始值值应为$f_{max}+1$,因为如果$r_{start}=f_{max}$,那么$mid=(l+2)>>1$恒小于$f_{max}$,即你永远不会尝试取走花费最大的点。

代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#define ll long long
#define INF 1000000000
#define re register

using namespace std;

long long read()
{
register long long x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}

long long n,m,u,v,s,ans,x,y,z,l,r,mid,cnt,flag,f[100005],d[100005],dis[100005],vis[100005];

struct edge{
long long to,nex,w;
}e[1000005];

struct node{
long long k,dis;
bool operator < (const node &x) const{return x.dis < dis;}
};

void add(long long x,long long y,long long z)
{
e[++cnt].to = y;
e[cnt].nex = d[x];
e[cnt].w = z;
d[x] = cnt;
}

priority_queue<node> que;

void dij()
{
while(!que.empty()) que.pop();
que.push((node){u,0});
while(!que.empty())
{
node u = que.top();
que.pop();
if(vis[u.k]) continue;
vis[u.k] = 1;
if(f[u.k] > mid) continue;
for(register int i = d[u.k]; i; i = e[i].nex)
{
if(f[e[i].to] > mid) continue;
if(dis[e[i].to] > dis[u.k] + e[i].w)
{
dis[e[i].to] = e[i].w + dis[u.k];
if(!vis[e[i].to]) que.push((node){e[i].to,dis[e[i].to]});
}
}
}
}

bool check(long long Max)
{
if(f[u] > Max || f[v] > Max) return false;
memset(dis,0x7f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[u] = 0;
dij();
if(dis[v] <= s) flag = 1;
if(dis[v] <= s) return true;
return false;
}

struct EDGE{
long long x,y,z;
}E[1000005];

bool cmp(EDGE a, EDGE b)
{
if(a.x != b.x) return a.x < b.x;
if(a.y != b.y) return a.y < b.y;
return a.z < b.z;
}

int main()
{
n = read(); m = read(); u = read(); v = read(); s = read();
for(int i = 1; i <= n; i++) f[i] = read(),r = max(r,f[i]);
r++;
for(int i = 1; i <= m; i++)
{
E[i].x = read();
E[i].y = read();
E[i].z = read();
}
sort(E + 1, E + m + 1, cmp);
for(int i = 1; i <= m; i++)
if((E[i].x != E[i - 1].x || E[i].y != E[i - 1].y) && E[i].x != E[i].y)
add(E[i].x,E[i].y,E[i].z),add(E[i].y,E[i].x,E[i].z);
while(l < r)
{
mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(flag == 0) printf("-1\n");
else printf("%lld\n",r);
return 0;
}
Author: wflight
Link: http://yoursite.com/2019/10/19/题解-P1951-【收费站-NOI导刊2009提高(2)】/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶

Comment