洛谷1462 通往奥格瑞玛的道路

本题地址： http://www.luogu.org/problem/show?pid=1462

思路：

　　先判断AFK的情况，以血量为权值，用SPFA算法计算一次最短路径，检查是否能在血量大于0的情况下到达终点。

　　然后，对各城市的过路费进行排序，用二分法依次尝试能否在不超过某费用的前提下经过各个城市且到达终点时血量大于0。

 1 #include <cstdio>
 2 #include <string.h>
 3 #include <deque>
 4 #include <algorithm>
 5 using namespace std;
 6 const int N = 1e4+10, M = 1e5+10;
 7 const long long int INF = (1LL<<61)-1;
 8 int u[M], v[M], w[M], first[N], Next[M], money[N], n, m, hp, a[N];
 9 long long int D[N];
10 bool cmp(const int a, const int b){
11     return money[a] < money[b];
12 }
13 bool SPFA(int cash)
14 {
15     for(int i=1; i<n; ++i)
16         D[i] = INF;
17     D[0] = 0;
18     bool cnt[N] = {0};
19     cnt[0] = true;
20     deque<int> dq;
21     int t;
22     dq.push_back(0);
23     while(!dq.empty())
24     {
25         t = dq.front();
26         dq.pop_front();
27         for(int x=first[t]; ~x; x=Next[x])
28         {
29             if(D[v[x]] > D[u[x]] + w[x] && money[v[x]] <= cash)
30             {
31                 D[v[x]] = D[u[x]] + w[x];
32                 if(!cnt[v[x]])
33                 {
34                     if(!dq.empty() && D[v[x]] < D[dq.front()])
35                         dq.push_front(v[x]);
36                     else
37                         dq.push_back(v[x]);
38                     cnt[v[x]] = true;
39                 }
40             }
41         }
42         cnt[t] = false;
43     }
44     return D[n-1] > hp ? false : true;
45 }
46 void solve(void)
47 {
48     if(!SPFA(1<<30))
49     {
50         printf("AFK
");
51         return ;
52     }
53     int l=0, r=n-1, mid, ans = 1<<30;
54     while(l<=r)
55     {
56         mid = (l+r)>>1;
57         if(SPFA(money[a[mid]]))
58             ans = money[a[mid]], r = mid-1;
59         else
60             l = mid+1;
61     }
62     printf("%d
", ans);
63 }
64 int main(void)
65 {
66     while(~scanf("%d %d %d", &n, &m, &hp))
67     {
68         memset(first, -1, sizeof(first));
69         for(int i=0; i<n; ++i)
70         {
71             a[i] = i;
72             scanf("%d", money+i);
73         }
74         sort(a, a+n, cmp);
75         for(int i=0; i<2*m; ++i)
76         {
77             scanf("%d %d %d", u+i, v+i, w+i);
78             --u[i], --v[i];
79             Next[i] = first[u[i]];
80             first[u[i]] = i++;
81             u[i] = v[i-1], v[i] = u[i-1], w[i] = w[i-1];
82             Next[i] = first[u[i]];
83             first[u[i]] = i;
84         }
85         solve();
86     }
87 }