题目链接：http://acm.scu.edu.cn/soj/problem.action?id=4527
题目：
题意：最短路的每条边除了边权之外还会有一个限制（财富，身上带的财富大于这个值则不能通过这条边），问能否在k的时间内逃离迷宫，能的话最多能携带多少财富。
思路：二分最终能携带的财富值，然后跑dijkstra。
代码实现如下：
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;;
typedef pair<int, int> pii;
typedef unsigned long long ull; #define lson i<<1
#define rson i<<1|1
#define bug printf("*********\n");
#define FIN freopen("D://code//in.txt", "r", stdin);
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define IO ios::sync_with_stdio(false),cin.tie(0); const double eps = 1e-;
const int mod = ;
const int mx = 1e4 + ;
const int maxn = 5e4 + ;
const double pi = acos(-);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f; int t, n, m, k, tot, u, v, w;
ll cap, ans;
int head[mx], vis[mx];
ll dis[mx]; struct edge {
int v, w, next;
ll cap;
}ed[maxn<<]; void addedge(int u, int v, int w, int cap) {
ed[tot].v = v;
ed[tot].w = w;
ed[tot].cap = cap;
ed[tot].next = head[u];
head[u] = tot++;
ed[tot].v = u;
ed[tot].w = w;
ed[tot].cap = cap;
ed[tot].next = head[v];
head[v] = tot++;
} void init() {
tot = ;
memset(head, -, sizeof(head));
} bool dij(ll x) {
memset(dis, inf, sizeof(dis));
memset(vis, , sizeof(vis));
priority_queue<pli, vector<pli>, greater<pli> > q;
q.push(make_pair(, ));
dis[] = ;
while(!q.empty()) {
int u = q.top().second; q.pop();
if(vis[u]) continue;
vis[u] = ;
for(int i = head[u]; ~i; i = ed[i].next) {
int v = ed[i].v;
if(ed[i].cap >= x && dis[v] > dis[u] + ed[i].w) {
dis[v] = dis[u] + ed[i].w;
q.push(make_pair(dis[v], v));
}
}
}
return dis[n] <= k;
} int main() {
//FIN;
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &m, &k);
init();
ll ub = , lb = , mid;
for(int i = ; i <= m; i++) {
scanf("%d%d%lld%d", &u, &v, &cap, &w);
addedge(u, v, w, cap);
if(cap > ub) ub = cap;
}
ans = -;
while(ub >= lb) {
mid = (ub + lb) >> ;
if(dij(mid)) {
lb = mid + ;
ans = mid;
}
else ub = mid - ;
}
if(ans != -) printf("%lld\n", ans);
else printf("Poor RunningPhoton!\n");
}
return ;
}