Luogu-P1462-通往奥格瑞玛的道路

Posted on Edited on Word count in article: 858

题目 P1462 通往奥格瑞玛的道路

题目背景

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

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

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

题目描述

在艾泽拉斯，有 nn 个城市。编号为 1,2,3,…,n1,2,3,\ldots,n。

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

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

假设 11 为暴风城，nn 为奥格瑞玛，而他的血量最多为 bb，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。

歪嘴哦不希望花很多钱，他想知道，在所有可以到达奥格瑞玛的道路中，对于每条道路所经过的城市收费的最大值，最小值为多少。

输入格式

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

接下来有 nn 行，每行 11 个正整数，fif_i。表示经过城市 ii，需要交费 fif_i 元。

再接下来有 mm 行，每行 33 个正整数，ai,bi,cia_i,b_i,c_i（1≤ai,bi≤n1\leq a_i,b_i\leq n）。表示城市 aia_i 和城市 bib_i 之间有一条公路，如果从城市 aia_i 到城市 bib_i，或者从城市 bib_i 到城市 aia_i，会损失 cic_i 的血量。

输出格式

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

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

思路：二分答案、最短路

二分答案的基本原理

问题转化

所求为交费，所以对交费进行二分答案。

将伤害视为边权，交费视为点权，将高交费的点舍去。

把路径长度看为边权和，方便处理血量。

二分

对于每个 moneymoney：

  • 在遍历边时，需要额外判断目标点的点权是否大于 moneymoney，若是则跳过。
  • 如果起始点的点权已经大于 moneymoney，直接结束判断。
  • 每次判断时，应该初始化。
  • 对于边权相关的量，使用long long类型存储（防止溢出）。

注意处理二分边界。

注意无向图需要开二倍空间（来回两条边）。

24/10/02 补充：

之所以二分可行，是因为给定了一个 moneymoney，有以下关系：

  • 比 moneymoney 小的不一定能通过，但是更优。
  • 比 moneymoney 大的一定能通过，但是更差。

也就是说，最优解一定小于等于 moneymoney。

因此，二分可行。

AC Code

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
// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template <typename T>
T d(T x){
    cout << x << endl;
    return x;
}

const int inf = 0x7f7f7f7f;

const int N = 1e4 + 10;
const int M = 5e4 * 2 + 10;
const int MAX = 1e9 + 10;

int cost[N];

int n, m;
ll health;

struct edge {
    int to, damage, next;
} edges[M];

int head[N];
int pt = 1;

bool vis[N];
ll dist[N];

struct node {
    int from;
    ll damage;
    bool operator<(const node &n) const {
        return damage > n.damage;
    }
};
priority_queue<node> q;


void add_edge(int from, int to, int damage) {
    edge &e = edges[pt];
    e.to = to;
    e.damage = damage;
    e.next = head[from];
    head[from] = pt++;
}

void init() {
    memset(dist, inf, sizeof dist);
    memset(vis, 0, sizeof vis);
    dist[1] = 0ll;
    q = priority_queue<node>();
}

bool check(int money) {
    if(money < cost[1]) return false;
    init();
    q.push({1, 0});
    while((q.size())) {
        node n = q.top();
        q.pop();
        int from = n.from;
        if(vis[from]) continue;
        vis[from] = true;
        for(int i = head[from]; i; i = edges[i].next) {
            edge e = edges[i];
            if(cost[e.to] > money) continue;
            if(vis[e.to]) continue;
            if(dist[e.to] > dist[from] + e.damage){
                dist[e.to] = dist[from] + e.damage;
                q.push({e.to, dist[e.to]});
            }
        }
    }
    return ((dist[n]) <= (health));
}

int get_ans() {
    int left = 1, right = MAX;
    int mid = (left + right) >> 1;
    while(left < right) {
        bool flag = check(mid);
        if(flag) {
            right = mid;
        } else {
            left = mid + 1;
        }
        mid = (left + right) >> 1;
    }
    return mid;
}

int main() {
    // freopen("test.in", "r", stdin);
    cin >> n >> m >> health;
    for(int i = 1; i <= n; i++) {
        cin >> cost[i];
    }
    int t1, t2, t3;
    for(int j = 1; j <= m; j++) {
        cin >> t1 >> t2 >> t3;
        add_edge(t1, t2, t3);
        add_edge(t2, t1, t3);
    }

    if((!check(MAX)))
        cout << "AFK" << endl;
    else
        cout << get_ans() << endl;

    return 0;
}

结语

算是独属于本题的特殊环节。

这道题的坑很多，我也自己创造了很多坑（看提交记录就能看出来）。

主要是以下问题：

  • 没关freopen（之所以开这个是因为测试数据的时候嫌控制台粘贴太慢了）。
  • 二分判断失误。
  • 不小心把退出条件写成了cost[e.to] >= money（应不含等于号）。

总之，这题虽然看着简单，但是实际操作会有很多的坑点需要注意。