洛谷1462 通往奥格瑞玛的道路二分+spfa

题目链接:

https://www.luogu.org/problem/show?pid=1462

题意:

题解:

二分法+最短路判定。

二分经过城市的最大费用w，然后判定：对于每一个费用大于w的城市标记为不可达，求最短路径，判断最短路与血量的关系即可。如果一个城市不可达可以在SPFA算法开始前将inq置为1。

小的优化：把f值从小到大排序，对f值进行二分就可以了。

代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define MS(a) memset(a,0,sizeof(a)) #define MP make_pair #define PB push_back const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } // const int maxn = 1e5+10; int n,m,B; ll f[maxn],x[maxn]; vector<pair<int,int> > E[maxn]; int inq[maxn]; ll d[maxn]; queue<int> q; bool check(ll w){ MS(inq); for(int i=1; i<=n; i++){ d[i] = INFLL; if(f[i] > w) inq[i] = 1; // 好神奇撒 到达了i这个点 也不会从i出发，保证i不可到达，特判终点就好了 } if(f[1]>w || f[n]>w) return false; queue<int> q; q.push(1),inq[1]=1,d[1]=0; while(!q.empty()){ int now = q.front(); q.pop(); inq[now] = 0; for(int i=0; i<(int)E[now].size(); i++){ int v = E[now][i].first; ll b = E[now][i].second; if(d[v] > d[now]+b){ d[v] = d[now]+b; if(inq[v]) continue; inq[v] = 1; q.push(v); } } } return B >= d[n]; } int main(){ cin >> n >> m >> B; for(int i=1; i<=n; i++) cin>>f[i]; for(int i=1; i<=m; i++){ int u,v,w; cin>>u>>v>>w; E[u].push_back(MP(v,w)); E[v].push_back(MP(u,w)); } memcpy(x,f,sizeof(f)); sort(x+1,x+n+1); int L = 1, R = n; ll ans = INFLL; while(L <= R){ int mid = (L+R)/2; if(check(x[mid])) ans=x[mid],R=mid-1; else L=mid+1; } if(ans==INFLL) puts("AFK"); else cout << ans << endl; return 0; }