【题解】P2387 [NOI2014] 魔法森林

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

给出一个有\(n\)个节点\(m\)条边的无向图，节点编号为\(1-n\)，边编号为\(1-m\)。初始时小E同学在\(1\)号节点。数据可能包含重边和自环。

每条边都有一个妖怪住在边上。在节点\(1\)处有两种守护精灵A，B，每种都有无数个。无向图中每条边都有权值\(a_i\)和\(b_i\)，当且仅当小E身上携带的A守护精灵不少于\(a_i\)，且B守护精灵不少于\(b_i\)，这条边上的妖怪不会对通过这条边的人发起攻击。

求在不被妖怪袭击的情况下，到\(n\)号节点最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。

\(2\le n \le 50000, 0\le m \le 100000, 1\le a_i,b_i \le 50000\)

分析

使用\(\text{SPFA}\)动态加点

按\(a\)的大小对边从小到大排序，再遍历边，每次将两个点入队进行\(\text{SPFA}\)。将b当作边权\(\text{SPFA}\)维护最大值: \[ ans=\min\{dis[n]+e[i].a\} \]

实现

\((100pts,683ms,11,,23mb)\)

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

#define ll long long
using namespace std;
const int N = 100005, INF = 0x3f3f3f3f;

ll ans = INF, n, m, x[N], y[N], head[N], tmp, dis[N];

bool vis[N];

struct node {
    int to, next, val;
} e[N << 2];

struct edge {
    int x, y, a, b;
} E[N << 1];

void add(int x, int y, int v) {
    e[++tmp].to = y;
    e[tmp].next = head[x];
    e[tmp].val = v;
    head[x] = tmp;
}

queue<ll> q;

inline void spfa(ll s, ll t) {
    vis[s] = vis[t] = true;
    q.push(s);
    q.push(t);
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        vis[x] = false;
        for (ll i = head[x]; i; i = e[i].next) {
            ll p = e[i].to, val = e[i].val;
            if (dis[p] > max(dis[x], val)) {
                dis[p] = max(dis[x], val);
                if (vis[p] == false) {
                    vis[p] = true;
                    q.push(p);
                }
            }
        }
    }

}

bool cmp(edge a, edge b) {
    return a.a < b.a;
}

ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}


int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        E[i].x = read(), E[i].y = read(), E[i].a = read(), E[i].b = read();
    }
    sort(E + 1, E + 1 + m, cmp);
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    q.push(1);
    vis[1] = true;
    for (ll i = 1; i <= m; i++) {
        add(E[i].x, E[i].y, E[i].b);
        add(E[i].y, E[i].x, E[i].b);
        spfa(E[i].x, E[i].y);
        ans = min(ans, dis[n] + E[i].a);
    }
    if (ans == INF) printf("-1\n");
    else printf("%lld\n", ans);

    return 0;
}