SCU 4527 NightMare2 最短路+二分好题-白红宇

SCU 4527 NightMare2 最短路+二分好题

阅读量：4684 次

发布时间：2019-06-09

本文共 3079 字，大约阅读时间需要 10 分钟。

可怜的

输入

第一行一个整数

每个样例的第一行有3个整数

输出

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

样例输入

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 知道二分的话还是很好写的

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
             9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #define pi acos(-1.0) 13 #define eps 1e-6 14 #define fi first 15 #define se second 16 #define lson l,m,rt<<1 17 #define rson m+1,r,rt<<1|1 18 #define bug printf("******\n") 19 #define mem(a,b) memset(a,b,sizeof(a)) 20 #define fuck(x) cout<<"["<
                
                 <<"]"<
                 
                  = b; i--) 28 #define FRL(i,a,b) for(i = a; i < b; i++) 29 #define FRLL(i,a,b) for(i = a; i > b; i--) 30 #define FIN freopen("DATA.txt","r",stdin) 31 #define gcd(a,b) __gcd(a,b) 32 #define lowbit(x) x&-x 33 #pragma comment (linker,"/STACK:102400000,102400000") 34 using namespace std; 35 typedef long long LL; 36 const int INF = 0x7fffffff; 37 const int maxn = 5e4 + 10; 38 int n, m, k, tot, head[maxn], d[maxn], val[maxn], vis[maxn]; 39 struct Edge { 40 int v, w, nxt, cost; 41 } edge[maxn * 10]; 42 struct node { 43 int v, d; 44 bool operator < (const node &b ) const { 45 return d > b.d; 46 } 47 node (int v, int d): v(v), d(d) {} 48 }; 49 void init() { 50 tot = 0; 51 mem(head, -1); 52 } 53 void add(int u, int v, int w, int cost) { 54 edge[tot].v = v; 55 edge[tot].w = w; 56 edge[tot].cost = cost; 57 edge[tot].nxt = head[u]; 58 head[u] = tot++; 59 } 60 61 int dijkstra(int mid) { 62 mem(vis, 0); 63 for (int i = 1 ; i <= n ; i++) d[i] = INF; 64 priority_queue
                  
                   que; 65 d[1] = 0; 66 que.push(node(1, 0)); 67 while(!que.empty()) { 68 node temp = que.top(); 69 que.pop(); 70 int u = temp.v; 71 if (vis[u]) continue; 72 vis[u] = 1; 73 for (int i = head[u] ; ~i ; i = edge[i].nxt) { 74 int v = edge[i].v, w = edge[i].w; 75 if ( !vis[v] && d[v] > d[u] + w && d[u]+w<=k &&edge[i].cost >= val[mid] ) { 76 d[v] = d[u] + w; 77 que.push(node(v, d[v])); 78 } 79 } 80 } 81 if (d[n] <= k) return 1; 82 return 0; 83 } 84 int main() { 85 int t; 86 sf(t); 87 while(t--) { 88 sfff(n, m, k); 89 init(); 90 int u, v, w; 91 for (int i = 0 ; i < m ; i++ ) { 92 sffff(u, v, val[i], w); 93 add(u, v, w, val[i]); 94 add(v, u, w, val[i]); 95 } 96 sort(val, val + m); 97 int len = unique(val, val + m) - val; 98 int low = 0, high = len - 1, mid, ans = -1; 99 while(low <= high) {100 int mid = (low + high) >> 1;101 if (dijkstra(mid)) {102 ans = mid;103 low = mid + 1;104 } else high = mid - 1;105 }106 if (ans == -1) printf("Poor RunningPhoton!\n");107 else printf("%d\n", val[ans]);108 }109 return 0;110 }