Magina

3
1 4
2 5 0
1 5
1 4 0
4 10
1 9 0
3 3 1
3
3 3 2
2 4
4 4 1
3

Case 1: 2
Case 2: Poor Magina, you can‘t save the world all the time!
Case 3: 10
题目大意：题目源自Dota，前面一堆介绍敌法师，最后一段才开始说有n堆野兽，每堆野兽屠杀完完需要花费ti时间，可以增加金钱gi，敌法师有瞬移技能，可以从某堆野兽移到另一堆野兽，题目给定相连的点。最后问求最少得到金钱m的情况下的最少时间。
解题思路：用深搜找出连通子图，然后在连通子图中的节点进行屠杀，每堆野兽有两种选择：杀获不杀.这样问题就转为01背包。
     但本题的金钱和屠杀时间范围都特别大，屠杀时间的范围是1-1000万，金钱的范围是1-10亿，不能用常规的两重循环模拟。其实用两个优先队列就可以模拟01背包的计算过程，第一次将（0，0）入队，然后出队转移到下一个状态，转移完这两个状态都进入队列，可以用两个优先队列进行操作，一个表示上一轮的计算结果，一个是这一轮,就相当于滚动数组。在用优先队列模拟的过程中要注意剪枝，如果不剪或者剪得不好就是MLE。只有一种可以，那就是在每次转移完要把队列1复制到队列0的时候，判断下入队的这个点是不是满足价值比前面入队的点金钱少且耗时少，如果是，这个可能比前面入队的那个优，如果不是，这个一定不须再加入队列，因为当前这个状态钱比进入队列的钱少，且用时相等或多，那么进入一个节点时进行更新一定不必先进队列的状态优。比如，（6，4）表示打到钱为6，且耗时4，如果下一个要进队的是(5,5)，那肯定是前面的更优，对吧？就是这样。
    
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;

const int inf=0xfffffff;

struct node
{
    int t,g;
    friend bool operator<(node a,node b)
    {
        if(a.g==b.g)
            return a.t>b.t;
        return a.g<b.g;
    }
};

int vist[55],M,ans;
vector<int>tmap[55];
priority_queue<node>q[2];
node val[55];

void dfs(int x)
{
    node p,tp;
    vist[x]=1;

    while(!q[0].empty())
    {
        p=q[0].top();
           q[0].pop();
        q[1].push(p);

        p.g+=val[x].g;
        p.t+=val[x].t;

        if(p.g>=M)
        {
            if(ans>p.t)ans=p.t; continue;
        }
        if(ans<=p.t)continue;

        q[1].push(p);
    }

    tp.t=ans;
    while(!q[1].empty())
    {
        p=q[1].top();
          q[1].pop();
        if(tp.t>p.t)
            q[0].push(p),tp=p;
    }

    for(int i=0;i<tmap[x].size();i++)
    {
        int j=tmap[x][i];
        if(vist[j])
            continue;
        dfs(j);
    }
}

int main()
{
    int T,N,k,u;
    node p;

    scanf("%d",&T);
    for(int c=1;c<=T;c++)
    {
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++)
        {
            tmap[i].clear();
            vist[i]=0;

            scanf("%d%d%d",&val[i].t,&val[i].g,&k);
            while(k--)
            {
                scanf("%d",&u); tmap[i].push_back(u);
            }
        }

        ans=inf;
        for(int s=1;s<=N;s++)
        if(vist[s]==0)
        {
            while(!q[0].empty()) q[0].pop();
            while(!q[1].empty()) q[1].pop();
            p.g=p.t=0;
            q[0].push(p);

            dfs(s);
        }

        printf("Case %d: ",c);
        if(ans!=inf)
        printf("%d\n",ans);
        else
        printf("Poor Magina, you can't save the world all the time!\n");
    }
}