洛谷P1462题解

发表于 | 更新于 | 评论数： | 阅读次数：

SPFA + 二分答案

题目背景

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

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

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

题目描述

在艾泽拉斯，有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。

INPUT & OUTPUT’s examples

Input’s e.g. #1

1
2
3
4
5
6
7
8
9
4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

Output’s e.g. #1

1
10

说明

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

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

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

分析

首先我们让题意说人话。

大体意思是某人要在一张无向图上从1号点走到第n号点，经过每一个点都要掉血掉钱，求一种方案能使这个人活着到达n号店并且交的钱（以下简称税收）最少。

题意简化之后明摆着是要大家二分。

题目要求求金钱的数量那就二分金钱即可。

那么我们二分的条件就是以当前值为最大值，判断是否有一条路径使得每条边的税收都$\leq$这个值，并且到n号点后，这个人还活着。

二分的边界就是这个人的血量$\leq 0$就算是结束。

我们寻找图上的最短路，如果这条路上所减少的血量足以致死，那么向上二分。

要是不足以致死，那么向下二分，缩小点权范围。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXM = 1e5 + 10;
const int MAXN = 1e4 + 10;
const int inf = INT_MAX;
int n,m,blood;
struct Edge{
    long long next,to,dis;
};
Edge Graph[MAXM];
int cnt,head[MAXN];
int dist[MAXN],Node[MAXN],weight[MAXN];
bool visited[MAXN];
/* functions */
inline void Add_Edge(long long from,long long to,long long cost){
    Graph[++cnt] = (Edge){head[from],to,cost};
    head[from] = cnt;
}
inline bool SPFA(int s){
    memset(visited,false,sizeof(visited));
    FOR(i,1,n,1)dist[i] = inf;
    std::queue<int> Q;
    Q.push(1);
    visited[1] = true; dist[1] = 0;
    int first;
    while(!Q.empty()){
        first = Q.front();
        Q.pop();
        visited[first] = false;
        for(int i=head[first];i;i=Graph[i].next){
            if((dist[Graph[i].to] > dist[first] + Graph[i].dis) && (weight[Graph[i].to] <= s)){
                dist[Graph[i].to] = dist[first] + Graph[i].dis;
                if(!visited[Graph[i].to]){
                    visited[Graph[i].to] = true;
                    Q.push(Graph[i].to);
                }
            }
        }
    }
    if(dist[n] <= blood)return true;//判断是否在收取费用为s时走完，如果最后扣血量会致死，表示不能通过
    else return false;
}
inline int binary_search(){
    int l = 1,r = n;
    int ans = 0;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(SPFA(Node[mid])){ans = Node[mid]; r = mid - 1;}
        else l = mid + 1;
    }
    return ans;
}
int main(int argc,char *argv[]){
    scanf("%d%d%d",&n,&m,&blood);
    FOR(i,1,n,1){scanf("%d",&weight[i]); Node[i] = weight[i];}
    FOR(i,1,m,1){
        long long u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        if(u == v)continue;
        Add_Edge(u,v,w);
        Add_Edge(v,u,w);
    }
    std::sort(Node+1,Node+n+1);
    if(SPFA(inf) == false){printf("AFK\n"); return 0;}
    int res = binary_search();
    print(res,false);
    return 0;
}

THE END