BZOJ3875 [AHOI2014]骑士游戏

2015.03.04 16:46 Wed| 3 visits oi_2015| 2015_刷题日常| Text

Solution

由于给出的不是拓扑图,可以类似于 SPFA 的方式解决。击杀一个怪兽的消耗改变的时候,击杀可以生成它的怪兽的消耗也就会随之降低。

注意,最开始击杀每一只怪兽的初始消耗都是魔法攻击的消耗值,因此需要全部塞到队列里面。

传说中,在 SPFA 内部每一次重新计算距离会 TLE,可是也仅仅用了 5 秒多。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 1000005
bool v[N];
int n;
long long s[N], k[N], r[N], d[N];
queue<int> q;
vector<int> son[N], fa[N];

inline long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void spfa()
{
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        v[x] = false;
        long long t = s[x];
        for (vector<int>::iterator i = son[x].begin(); i != son[x].end(); ++i)
            t += d[*i];
        if (t >= d[x]) continue;
        d[x] = t;
        for (vector<int>::iterator i = fa[x].begin(); i != fa[x].end(); ++i)
            if (!v[*i]) v[*i] = true, q.push(*i);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        s[i] = read(); k[i] = read(); r[i] = read();
        for (int x, j = 1; j <= r[i]; ++j)
            son[i].push_back(x = read()), fa[x].push_back(i);
        d[i] = k[i]; q.push(i); v[i] = true;
    }
    spfa();
    cout << d[1] << endl;
}