P1462 通往奥格瑞玛的道路

提交 29.89k

通过 6.88k

时间限制 1.00s

内存限制 125.00MB

题目提供者 gconeice

难度提高+/省选-

历史分数100

提交记录

查看题解

题目背景

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量

有一天他醒来后发现自己居然到了联盟的主城暴风城

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛

题目描述

在艾泽拉斯，有n个城市。编号为1,2,3,...,n。

城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设1为暴风城，n为奥格瑞玛，而他的血量最多为b，出发时他的血量是满的。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

输入格式

第一行3个正整数，n，m，b。分别表示有n个城市，m条公路，歪嘴哦的血量为b。

接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。

再接下来有m行，每行3个正整数，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi，或者从城市bi到城市ai，会损失ci的血量。

输出格式

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出AFK。

输入输出样例

输入 #1

输出 #1

说明/提示

对于60%的数据，满足n≤200，m≤10000，b≤200

对于100%的数据，满足n≤10000，m≤50000，b≤1000000000

对于100%的数据，满足ci≤1000000000，fi≤1000000000，可能有两条边连接着相同的城市。

题意：找到一条从 1 到 n 的路，且满足路上在某个点交过路费的最大值要最小。

思路

　　因为血量有限而钱无限，所以显然我们是要找一条能活着走完的路，并且还要满足要求。

　　所有类似于“求解所有的最大值中的最小值”的问题，并且满足单调，都可以想到二分法。

　　把扣血量看作边长，在dijkstra的过程中，对于更新dis时，需要再添加一个限制条件 f [i] <= mid 来逐渐放宽我们可以走的点的范围，以此来保证一定可以走出一条血不会被扣完且收费的最大值最小的一条路。

ＣＯＤＥ

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e5 + 7;
 47 const int inf  = 0x3f3f3f3f;
 48 
 49 int head[maxn << 1], edge[maxn << 1], w[maxn << 1], nxt[maxn << 1];
 50 int cnt, b;
 51 int f[maxn << 1];
 52 
 53 inline void BuildGraph (int u, int v, int c) {
 54     cnt++;
 55     edge[cnt] = v;
 56     nxt[cnt]  = head[u];
 57     w[cnt] = c;
 58     head[u] = cnt;
 59 }
 60 
 61 struct node {
 62     int u,v;
 63     bool operator <(const node &t) const {
 64         return u > t.u;
 65     }
 66 };
 67 
 68 int n,m,s,t,maxx;
 69 int dis[maxn];
 70 
 71 priority_queue < node > q;
 72 
 73 bool check(int x) {
 74     if(x < f[1])
 75         return 0;
 76     for (int i = 1; i <= n; ++i) {
 77         dis[i] = inf;
 78     }
 79     dis[1] = 0;
 80     node temp;
 81     temp.u = 0;
 82     temp.v = 1;
 83     q.push(temp);
 84     while(!q.empty()) {
 85         int u = q.top().v;
 86         int d = q.top().u;
 87         q.pop();
 88         if(d != dis[u]) continue;
 89         for (int i = head[u]; i; i = nxt[i]) {
 90             int v = edge[i];
 91             int c = w[i];
 92             if(dis[v] > dis[u] + c && f[v] <= x) {
 93                 dis[v] = dis[u] + c;
 94                 node p;
 95                 p.u = dis[v], p.v = v;
 96                 q.push(p);
 97             }
 98         }
 99     }
100     if(dis[n] < b) {
101         return 1;
102     }
103     return 0;
104 }
105 
106 int main()
107 {
108     scanf("%d %d %d",&n,&m,&b);
109     for (int i = 1; i <= n; ++i) {
110         scanf("%d",&f[i]);
111         maxx = max(maxx, f[i]);
112     }
113     for (int i = 1; i <= m; i++) {
114         int u, v, c;
115         scanf("%d %d %d",&u,&v,&c);
116         BuildGraph(u, v, c);
117         BuildGraph(v, u, c);
118     }
119     if(!check(inf)) {
120         puts("AFK");
121         return 0;
122     }
123     int l = 1, r = inf, mid = (l + r) >> 1;
124     while(l <= r) {
125         if(check(mid)) {
126             r = mid - 1;
127             mid = (l + r) >> 1;
128         }
129         else {
130             l = mid + 1;
131             mid = (l + r) >> 1;
132         }
133     }
134     printf("%d\n",l);
135 
136     return 0;
137 }

View Code

P1462 通往奥格瑞玛的道路【二分+Dij】