Luogu P1462 通往奥格瑞玛的道路

  • 博客挺久没更新了,准备今天多更新点

  • 九月份也开始停课了,但是还是很慌,如果各方大佬看到,就当作个笑话好了qwq

这是九月三号做的题, 到现在也已经十天了,都快忘了。

  • 这是一道图论上的二分题,二分一下答案,也就是二分缴费最多的一次的费用,check函数是最短路,限制最短路:如果在最短路过程中, 遇到一个城市需要交的费用大于mid,就忽略这个城市,这样跑一次最短路,看一下从1到n血量会不会减到小于0,如果小于0,考虑了l = mid + 1,否则考虑mid = r
  • 代码:
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Solution{
int n, m;
ll b, maxv;
vector<vector<pair<int, ll> > > e;
vector<ll> v;

bool dijkstra(int s, ll limit){
vector<ll> d;
vector<bool> vis;
vis.resize(n + 1);
d.resize(n + 1, 0x3f3f3f3f3f3f3f3f);
priority_queue<pair<ll, int> > pq;
d[s] = 0;
pq.push(make_pair(-d[s], s));
while(!pq.empty()){
int x = pq.top().second;
pq.pop();
for(int i = 0; i < e[x].size(); i++){
int y = e[x][i].first;
int value = e[x][i].second;
if(vis[y] || v[y] > limit) continue;
vis[y] = 1;
if(d[y] > d[x] + value){
d[y] = d[x] + value;
pq.push(make_pair(-d[y], y));
}
}
}
if(d[n] >= b) return 0;
else return 1;
}

void Solve(){
maxv = 0;
scanf("%d%d%lld", &n, &m, &b);
v.resize(n + 1);
for(int i = 1; i <= n; i++) scanf("%lld", &v[i]), maxv = max(maxv, v[i]);
e.resize(n + 1);
for(int i = 1; i <= m; i++){
int x, y;
ll w;
scanf("%d%d%lld", &x, &y, &w);
e[x].push_back(make_pair(y, w));
e[y].push_back(make_pair(x, w));
}
ll l = 0, r = maxv + 10;
while(l < r){
ll mid = (l + r) / 2;
if(dijkstra(1, mid)) r = mid;
else l = mid + 1;
}
if(l > maxv) printf("AFK\n");
else printf("%lld\n", l);
}
};

int main(){
Solution().Solve();
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×