Mr. Panda and Crystal HDU

Panda and Crystal HDU"/>

Mr. Panda and Crystal HDU

题目链接

我特么的太激动了，读完题以后我就懵懵懂懂的觉得要用完全背包！！！我竟然看出来这是一道DP了！！！然而这道题还要求出创造每种水晶的最低成本，题解说是要用最短路，不知道为什么就很喜欢最短路，可能是我认真学习的算法吧。认真学习真的是一件很棒的事情啊。

最短路合成每种水晶的最小成本，完全背包解决，完美吗？？？

啊啊啊最短了RE到死，问了一下过了这题的大佬，INF和数相加就会爆int变成负数，这个数作为数组下标就会RE，把INF改成比给出的魔力值稍大一点的数就AC了,开心。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1e9 + 7
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn = 1e4 + 10;
int dp[maxn],d[210];
struct edge
{int id;vector<P> pa;
}edges[210];
struct node
{int a,b;
}node[210];
struct poin
{int v,w;poin(int a,int b):v(a),w(b){}bool operator < (poin p)const{return w > p.w;}
};
vector<int> g[210];
priority_queue<poin> q;
int get_sum(edge e)
{int sum = 0;for(int i = 0;i < e.pa.size();i++){sum += d[e.pa[i].first] * e.pa[i].second;}return sum;
}
void Dijkstra()
{while(!q.empty()){poin now = q.top(); q.pop();if(d[now.v] < now.w) continue;for(int i = 0;i < g[now.v].size();i++){edge & e = edges[g[now.v][i]];int sum = get_sum(e);if(d[e.id] > sum){d[e.id] = sum;node[e.id].b = d[e.id];q.push(poin(e.id,d[e.id]));}}}
}
void init()
{memset(dp,0,sizeof(dp));memset(d,INF,sizeof(d));memset(edges,0,sizeof(edges));while(!q.empty()) q.pop();
}
int main()
{int T;scanf("%d",&T);for(int K = 1;K <= T;K++){int n,m,k;init();scanf("%d%d%d",&n,&m,&k);for(int i = 1;i <= m;i++){int s,x,y;g[i].clear();scanf("%d",&s);if(s == 0){scanf("%d",&y);node[i].a = y;d[i] = node[i].b = n + 1;//!!!注意这里用INF回RE，大佬说爆int相加以后为负数，用作数组下标就RE了}else if(s == 1){scanf("%d%d",&x,&y);node[i].a = y;d[i] = node[i].b = x;}}for(int i = 1;i <= k;i++){int a,b,x,y;scanf("%d%d",&a,&b);edges[i].id = a;for(int j = 1;j <= b;j++){scanf("%d%d",&x,&y);edges[i].pa.push_back(P(x,y));g[x].push_back(i);}}for(int i = 1;i <= m;i++){if(d[i] <= n){q.push(poin(i,d[i]));}}Dijkstra();int ans = 0;for(int i = 1;i <= m;i++){for(int j = node[i].b;j <= n;j++){dp[j] = max(dp[j],dp[j - node[i].b] + node[i].a);}}printf("Case #%d: %d\n",K,dp[n]);}return 0;
}