SCU 4527 NightMare2 最短路+二分 好题

时间：2022-02-05 18:43:13

可怜的又做噩梦了。。但是这次跟上次不大一样，虽然他又被困在迷宫里，又被装上了一个定时炸弹，但是值得高兴的是，他发现他身边有数不清的财宝，所以他如果能带着这些财宝并活着逃出去的话，他就发财啦。不过，这次的迷宫不再是一个矩形方格了，而是由点和边组成的图，每条边都有通过该边的时间，以及由于神奇阵法而产生的对财宝数量的限制（即通过这条边只能带上不超过一定数量的财宝，否则炸弹将笋干爆炸！）。现在，又开始疑惑了，在保证能活着逃出去的情况下，他最多能拿多少价值的财宝？

 

输入

第一行一个整数，代表样例数。 
每个样例的第一行有3个整数,分别代表迷宫的点数，边数以及炸弹离爆炸的剩余时间。刚开始在，出口在。 
接下来行，每行4个整数分别代表每条边的两端点，该边的财宝数量限制以及通过这条边的时间。 
（ 这次在计时到的时候到达点也算逃出迷宫）

 

输出

每组数据输出一行，代表在保证或者逃出去的情况下能得到的最多财宝价值，被炸死输出"Poor RunningPhoton!"(不含引号)。

 

样例输入

2 
2 1 10 
1 2 13 10 
4 4 20 
1 2 1000 15 
2 4 999 6 
1 3 100 15 
3 4 99 4

这题帮助理解dijstra 知道二分的话还是很好写的

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <cmath>

 #include <algorithm>

 #include <set>

 #include <iostream>

 #include <map>

 #include <stack>

 #include <string>

 #include <vector>

 #define  pi acos(-1.0)

 #define  eps 1e-6

 #define  fi first

 #define  se second

 #define  lson l,m,rt<<1

 #define  rson m+1,r,rt<<1|1

 #define  bug         printf("******\n")

 #define  mem(a,b)    memset(a,b,sizeof(a))

 #define  fuck(x)     cout<<"["<<x<<"]"<<endl

 #define  sf(n)       scanf("%d", &n)

 #define  sff(a,b)    scanf("%d %d", &a, &b)

 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)

 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)

 #define  pf          printf

 #define  FRE(i,a,b)  for(i = a; i <= b; i++)

 #define  FREE(i,a,b) for(i = a; i >= b; i--)

 #define  FRL(i,a,b)  for(i = a; i < b; i++)

 #define  FRLL(i,a,b) for(i = a; i > b; i--)

 #define  FIN freopen("DATA.txt","r",stdin)

 #define  gcd(a,b) __gcd(a,b)

 #define  lowbit(x)   x&-x

 #pragma  comment (linker,"/STACK:102400000,102400000")

 using namespace std;

 typedef long long LL;

 const int INF = 0x7fffffff;

 const int maxn = 5e4 + ;

 int n, m, k, tot, head[maxn], d[maxn], val[maxn], vis[maxn];

 struct Edge {

     int v, w, nxt, cost;

 } edge[maxn * ];

 struct node {

     int v, d;

     bool operator < (const node &b ) const {

         return d > b.d;

     }

     node (int v, int d): v(v), d(d) {}

 };

 void init() {

     tot = ;

     mem(head, -);

 }

 void add(int u, int v, int w, int cost) {

     edge[tot].v = v;

     edge[tot].w = w;

     edge[tot].cost = cost;

     edge[tot].nxt = head[u];

     head[u] = tot++;

 }

 int dijkstra(int mid) {

     mem(vis, );

     for (int i =  ; i <= n ; i++) d[i] = INF;

     priority_queue<node>que;

     d[] = ;

     que.push(node(, ));

     while(!que.empty()) {

         node temp = que.top();

         que.pop();

         int u = temp.v;

         if (vis[u]) continue;

         vis[u] = ;

         for (int i = head[u] ; ~i ; i = edge[i].nxt) {

             int v = edge[i].v, w = edge[i].w;

             if ( !vis[v] && d[v] > d[u] + w && d[u]+w<=k  &&edge[i].cost >= val[mid] ) {

                 d[v] = d[u] + w;

                 que.push(node(v, d[v]));

             }

         }

     }

     if (d[n] <= k) return ;

     return ;

 }

 int  main() {

     int t;

     sf(t);

     while(t--) {

         sfff(n, m, k);

         init();

         int u, v, w;

         for (int i =  ; i < m ; i++ ) {

             sffff(u, v, val[i], w);

             add(u, v, w, val[i]);

             add(v, u, w, val[i]);

         }

         sort(val, val + m);

         int len = unique(val, val + m) - val;

         int low = , high = len - , mid, ans = -;

         while(low <= high) {

             int mid = (low + high) >> ;

             if (dijkstra(mid)) {

                 ans = mid;

                 low = mid + ;

             } else high = mid - ;

         }

         if (ans == -) printf("Poor RunningPhoton!\n");

         else printf("%d\n", val[ans]);

     }

     return ;

 }

相关文章