题目链接：http://acm.scu.edu.cn/soj/problem.action?id=4527
题目：
题意：最短路的每条边除了边权之外还会有一个限制（财富，身上带的财富大于这个值则不能通过这条边），问能否在k的时间内逃离迷宫，能的话最多能携带多少财富。
思路：二分最终能携带的财富值，然后跑dijkstra。
代码实现如下：
?1 #include <set> ?2 #include <map> ?3 #include <queue> ?4 #include <stack> ?5 #include <cmath> ?6 #include <bitset> ?7 #include <cstdio> ?8 #include <string> ?9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 ?16 typedef long long ll; 17 typedef pair<ll, ll> pll; 18 typedef pair<ll, int> pli; 19 typedef pair<int, ll> pil;; 20 typedef pair<int, int> pii; 21 typedef unsigned long long ull; 22 ?23 #define lson i<<1 24 #define rson i<<1|1 25 #define bug printf("*********\n"); 26 #define FIN freopen("D://code//in.txt", "r", stdin); 27 #define debug(x) cout<<"["<<x<<"]" <<endl; 28 #define IO ios::sync_with_stdio(false),cin.tie(0); 29 ?30 const double eps = 1e-8; 31 const int mod = 10007; 32 const int mx = 1e4 + 7; 33 const int maxn = 5e4 + 7; 34 const double pi = acos(-1); 35 const int inf = 0x3f3f3f3f; 36 const ll INF = 0x3f3f3f3f3f3f3f; 37 ?38 int t, n, m, k, tot, u, v, w; 39 ll cap, ans; 40 int head[mx], vis[mx]; 41 ll dis[mx]; 42 ?43 struct edge { 44 ????int v, w, next; 45 ????ll cap; 46 }ed[maxn<<2]; 47 ?48 void addedge(int u, int v, int w, int cap) { 49 ????ed[tot].v = v; 50 ????ed[tot].w = w; 51 ????ed[tot].cap = cap; 52 ????ed[tot].next = head[u]; 53 ????head[u] = tot++; 54 ????ed[tot].v = u; 55 ????ed[tot].w = w; 56 ????ed[tot].cap = cap; 57 ????ed[tot].next = head[v]; 58 ????head[v] = tot++; 59 } 60 ?61 void init() { 62 ????tot = 0; 63 ????memset(head, -1, sizeof(head)); 64 } 65 ?66 bool dij(ll x) { 67 ????memset(dis, inf, sizeof(dis)); 68 ????memset(vis, 0, sizeof(vis)); 69 ????priority_queue<pli, vector<pli>, greater<pli> > q; 70 ????q.push(make_pair(0, 1)); 71 ????dis[1] = 0; 72 ????while(!q.empty()) { 73 ????????int u = q.top().second; q.pop(); 74 ????????if(vis[u]) continue; 75 ????????vis[u] = 1; 76 ????????for(int i = head[u]; ~i; i = ed[i].next) { 77 ????????????int v = ed[i].v; 78 ????????????if(ed[i].cap >= x && dis[v] > dis[u] + ed[i].w) { 79 ????????????????dis[v] = dis[u] + ed[i].w; 80 ????????????????q.push(make_pair(dis[v], v)); 81 ????????????} 82 ????????} 83 ????} 84 ????return dis[n] <= k; 85 } 86 ?87 int main() { 88 ????//FIN; 89 ????scanf("%d", &t); 90 ????while(t--) { 91 ????????scanf("%d%d%d", &n, &m, &k); 92 ????????init(); 93 ????????ll ub = 0, lb = 0, mid; 94 ????????for(int i = 1; i <= m; i++) { 95 ????????????scanf("%d%d%lld%d", &u, &v, &cap, &w); 96 ????????????addedge(u, v, w, cap); 97 ????????????if(cap > ub) ub = cap; 98 ????????} 99 ????????ans = -1;100 ????????while(ub >= lb) {101 ????????????mid = (ub + lb) >> 1;102 ????????????if(dij(mid)) {103 ????????????????lb = mid + 1;104 ????????????????ans = mid;105 ????????????}106 ????????????else ub = mid - 1;107 ????????}108 ????????if(ans != -1) printf("%lld\n", ans);109 ????????else printf("Poor RunningPhoton!\n");110 ????}111 ????return 0;112 }NightMare2（SCU4527+dijkstra+二分）
原文地址：https://www.cnblogs.com/Dillonh/p/9427672.html