[HDU - 6007] Mr. Panda and Crystal

题意：

你有m个魔法值，现在有n个水晶（这n个水晶可以用魔法值合成，有的不能）每个水晶都有一个价值，还能通过k个公式用别的水晶合成水晶。问用现有的魔法值能赚多少钱？

---

分析：

首先用最短路求出通过各个公式合成第i个水晶所需的最小魔法值，再跑完全背包。
说起来简单。。。实现起来非常麻烦。。。
比较重要的一个点是需要建一个vector，存的是原料为第i种水晶的都有几号公式。建这个vector是跑spfa用的，当发现第i个水晶需要的魔法值发生变化后，所有以第i个水晶为原料的公式最后合成需要的费用都会改变，所以都需要放进队列里，这个vector就是为了找以第i个水晶为原料的公式的。

---

题目：

Problem Description
Long long time ago, there is a magic continent far far away.
There are N types of magic crystals that contain ancient magic powers. Each of the type of magic crystal has its own price for one piece in the market. As the most powerful magician, Mr. Panda could synthesize some types of crystals by collecting some amount of other types of crystals. He could also create some types of crystals by using some number of his magic powers.
Now, Mr Panda can create any number of crystals as he wish by using no more than M magic powers. He want to know the maximum amount of money he can make by sell all the crytals he creates and synthesizes.

Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with 3 positive intergers, M, N and K represent the amount of magic powers Mr. Panda had, the number of crystal types on the magic continent and the number of crystal synthesis equations.
Then N lines follows, each of them starts with one 0 or 1 which indicates whehter Mr. Panda could create this type of crystal.
If the ith line starts with 0, which means Mr. Panda couldn’t create crystal type i. Then there is one integer pi in this line which is the price for each piece of crystal type i.
If the ith line starts with 1, which means Mr. Panda could create crystal type i. Then there are two positive integers ci and pi in this line, the first is the amout of magic power cost when creates one piece of crystal type i, and the second is is the price for each piece of crystal type i.
The following K lines each start with two interger xi and yi , which means for synthesizing one piece of crystal type xi , yi rules should be satisfied. Then there are yi pair of positive intergers uj and vj means for one piece of xthi type cristal, we have to collect vi piece of crystal type ui. Only when all the rules of ui and vi are satisfied, Mr. Panda could synthesize one piece xthi type cristal.

Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximum amout of money Mr. Panda could make.
limits

∙1≤T≤100.
∙1≤M≤10000.
∙1≤N≤200.
∙1≤K≤200.
∙1≤xi,uj≤N.
∙foreachcrystalsynthesisequation,allujaredifferent.
∙1≤vj≤100.
∙1≤ci,pi≤10000.

Sample Input

2
100 3 2
0 20
1 15 10
1 2 1
1 2 2 1 3 1
2 1 3 2
100 3 2
1 3 1
1 4 1
0 10
3 1 1 3
3 1 2 2

Sample Output

Case #1: 330
Case #2: 121

---

代码：

#include <bits/stdc++.h>

using namespace std;

const long long inf = 0x3f3f3f3f;
const int maxn = 1010;

struct crystal
{
    int creat, price;
    long long cost;
}data[maxn];
long long dis[maxn];
int cases, n, power, k;
struct Edge
{
    int to, weight;
    Edge(int to, int weight): to(to), weight(weight){};
};

vector<Edge> v[maxn];
vector<pair<int, int> > vv[maxn];
int dest[maxn];
vector<int> vvv[maxn];

void spfa()
{
    queue <int> que;
    for (int i = 0; i < k; i++)
    {
        long long sum = 0;
        bool ok = 1;
        for (int j = 0; j < vv[i].size(); j++)
        {
            if (vv[i][j].second == inf)
            {
                ok  = false;
                break;
            }
            sum += dis[vv[i][j].first] * vv[i][j].second;
        }
        if (!ok)
            continue;
        int inq[maxn] = {0};
        if (dis[dest[i]] > sum)
        {
            que.push(dest[i]);
            dis[dest[i]] = sum;
        }
        else
            continue;
        inq[dest[i]] = 1;
        while (!que.empty())
        {
            int cur = que.front();
            que.pop();
            inq[cur] = 0;
            for (int j = 0; j < vvv[cur].size(); j++)
            {
                int sub = vvv[cur][j];//sub是几号公式
                sum = 0;
                for (int l = 0; l < vv[sub].size(); l++)
                    sum += vv[sub][l].second * dis[vv[sub][l].first];
                if (dis[dest[sub]] > sum)
                {
                    dis[dest[sub]] = sum;
                    if (!inq[dest[sub]])
                    {
                        que.push(dest[sub]);
                        inq[dest[sub]] = 1;
                    }
                }
            }
        }
    }
}

long long dp[10005];
int main()
{
    scanf("%d", &cases);
    for (int c = 1; c <= cases; c++)
    {
        for (int i = 0; i < maxn; i++)
        {
            v[i].clear();
            vv[i].clear();
            vvv[i].clear();
        }
        memset(dis, 0x3f, sizeof(dis));
        scanf("%d %d %d", &power, &n, &k);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &data[i].creat);
            if (data[i].creat)
                scanf("%lld", &data[i].cost);
            else
                data[i].cost = inf;
            dis[i] = data[i].cost;
            scanf("%d", &data[i].price);
            v[0].push_back(Edge(i, data[i].cost));
        }
        for (int i = 0; i < k; i++)
        {
            int to, need, id, num;
            scanf("%d %d", &to, &need);
            for (int j = 1; j <= need; j++)
            {
                scanf("%d %d", &id, &num);
                vv[i].push_back(make_pair(id, num));
                vvv[id].push_back(i);
                dest[i] = to;
            }
        }
        spfa();
//        for (int i = 1; i <= n; i++)
//            printf("%d号的费用为%lld\n", i, dis[i]);
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
        {
            int v, w;
            v = dis[i];
            w = data[i].price;
            for(int j = v; j <= power; j++)
                dp[j] = max(dp[j], dp[j - v] + w);
        }
        printf("Case #%d: %lld\n", c, dp[power]);
    }
    return 0;
}