Luogu P1462 通往奥格瑞玛的道路

思路

对于不能到达的情况，直接跑一遍$SPFA$就可以了

使得最大值最下，这不是典型的二分答案吗

二分最大的费用

后面用$SPFA$实现，只需要在进行松弛操作的时候进行一下调整

使得所有沿途的点的话费都小于这个二分出来的花费

 

代码

#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cstring> #define MAXN 10007 #define MAXm 100007 #define INF 2147483647 #define int long long using namespace std; int n, m, b, f[MAXN], first[MAXN], dis[MAXN], s = 1; int u[MAXm], v[MAXm], w[MAXm], next[MAXm], maxn, Ans; bool vis[MAXN]; deque<int> Q; bool SPFA(int s, int p) { if(f[1] >= p) return false; memset(vis, false, sizeof(vis)); for(int i=1; i<=n; i++) {dis[i] = INF;} dis[s] = 0; while(!Q.empty()) {Q.pop_front();} Q.push_front(s); vis[s] = 1; while(!Q.empty()) { int x = Q.front(); int k = first[Q.front()]; Q.pop_front(); while(k != -1) { if(dis[v[k]] > dis[u[k]]+w[k]&&f[v[k]] <= p) { dis[v[k]] = dis[u[k]]+w[k]; if(!vis[v[k]]) { vis[v[k]] = 1; if(dis[v[k]] > dis[x]) Q.push_back(v[k]); else Q.push_front(v[k]); } } k = next[k]; } vis[x] = 0; } if(dis[n] < b) return true; else return false; } main() { scanf("%lld%lld%lld", &n, &m, &b); for(int i=1; i<=n; i++) {scanf("%lld", &f[i]); maxn = max(maxn, f[i]);} memset(first, -1, sizeof(first)); for(int i=1; i<=n; i++) {dis[i] = INF;} dis[s] = 0; for(int i=1; i<=2*m; i++) { scanf("%lld%lld%lld", &u[i], &v[i], &w[i]); next[i] = first[u[i]]; first[u[i]] = i; i++; u[i] = v[i-1], v[i] = u[i-1], w[i] = w[i-1]; next[i] = first[u[i]]; first[u[i]] = i; } int l = 1, r = maxn; bool mark = false; while(l <= r) { int mid = (l+r)/2; if(SPFA(1, mid)) { r = mid-1; mark = true; } else l = mid+1; } if(mark == false) printf("AFK"); else printf("%lld\n", l); return 0; }

 

转载于:https://www.cnblogs.com/bljfy/p/9269867.html

相关资源：数据结构—成绩单生成器