zoj 3524 Crazy Shopping

zoj 3524 Crazy Shopping

#include <iostream>#include <string>#include <map>#include <queue>#include <stack>#include <algorithm>#include <list>#include <set>#include <cmath>#include <cstring>#include <stdio.h>#include <string.h>#include <sstream>#include <stdlib.h>#include <vector>#include <iomanip>#include <ctime>#include <assert.h>using namespace std;typedef long long ll;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<vi>vvi;typedef vector<string> vs;typedef map<string,int> msi;typedef map<int,int>mii;#define ERR 1e-9#define PI 3.141592653589793#define REP(i,n) for (i=0;i<n;i++)#define FOR(i,p,k) for (i=p; i<k;i++)#define FOREACH(it,x) for(__typeof((x).begin()) it=(x.begin()); it!=(x).end(); ++it)#define Sort(x) sort(x.begin(),x.end())#define Reverse(x) reverse(x.begin(),x.end())#define MP(a,b) make_pair(a,b)#define Clear(x,with) memset(x,with,sizeof(x))#define SZ(x) (int)x.size()#define pb push_back#define popcount(i) __builtin_popcount(i)#define gcd(a,b) __gcd(a,b)#define lcm(a,b) ((a)*((b)/gcd(a,b)))#define two(X) (1<<(X))#define twoL(X) (((ll)(1))<<(X))#define setBit(mask,i) (mask|two(i))#define contain(S,X) (((S)&two(X))!=0)#define fs first#define sc second#define CS c_str()#define EQ(a,b) (fabs(a-b)<ERR)#define Unique(store) store.resize(unique(store.begin(),store.end())-store.begin());#define Find(x,y) ((int)x.find(y))#define debug_array(a,n) for(int i=0;i<n;i++) cerr<<a[i]<<" "; cerr<<endl;#define debug_matrix(mat,row,col) for(int i=0;i<row;i++) {for(int j=0;j<col;j++) cerr<<mat[i][j]<<" ";cerr<<endl;}#define debug(args...) {dbg,args; cerr<<endl;}struct debugger{template<typename T> debugger& operator , (const T& v){cerr<<v<<"t"; return *this; }}dbg;template<class T> void setmax(T &a, T b) { if(a < b) a = b; }template<class T> void setmin(T &a, T b) { if(b < a) a = b; }template<class T> T Abs(T x) {return x > 0 ? x : -x;}template<class T> inline T sqr(T x){return x*x;}template<class T> inline T Mod(T n,T m) {return (n%m+m)%m;} template<class T> string toString(T n){ostringstream oss;oss<<n;oss.flush();return oss.str();}int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}bool isVowel(char ch){ch=tolower(ch);if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u')return true;return false;}bool isUpper(char c){return c>='A' && c<='Z';}bool isLower(char c){return c>='a' && c<='z';}ll Pow(ll B,ll P){ll R=1;while(P>0){if(P%2==1)R=(R*B);P/=2;B=(B*B);}return R;}int BigMod(ll B,ll P,ll M){ll R=1;while(P>0){if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;}return (int)R;}void binprint(ll mask,ll n){ll i;string s="";do{s+=(mask%2+'0');mask/=2;}while(mask);Reverse(s);s=string(max(n-SZ(s),0LL),'0')+s;for(i=SZ(s)-n;i<SZ(s);i++) printf("%c",s[i]);printf("n");}void ASCII_Chart(){int i,j,k;printf("ASCII Chart:(30-129)n");FOR(i,30,50){REP(j,5){k=i+j*20;printf("%3d---> '%c' ",k,k);}printf("n");}}#define INF (1<<28)#define SIZE 1100pair<ll,ll> dp[610][2010];int W,N,M,X,Case,wei[610],val[610];int color[610][2010];vector<pii> adj[610];pair<ll,ll> rec(int u,int taken){ if(taken>W) return MP(-INF,0); if(taken==W) return MP(0,0); pair<ll,ll> &ret = dp[u][taken], tmp; if(color[u][taken]==Case) return ret; color[u][taken] = Case; ret = MP(0,0); tmp = rec(u,taken+wei[u]); tmp.fs+=val[u]; if(tmp.fs>ret.fs || (tmp.fs==ret.fs&&tmp.sc<ret.sc)) ret = tmp; int next = -1; for(int i=0;i<SZ(adj[u]);i++) { int v = adj[u][i].fs; ll c = adj[u][i].sc; tmp = rec(v,taken); tmp.sc += c*taken; if(tmp.fs>ret.fs) { ret = tmp; next = v; } else if(tmp.fs==ret.fs && tmp.sc<ret.sc) { ret = tmp; next = v; } } return ret;}int main(){ int i,j,test,u,v,c; Case = 1; while(scanf("%d %d %d %d",&N,&M,&W,&X)==4) { for(i=1;i<=N;i++) adj[i].clear(); for(i=1;i<=N;i++) scanf("%d %d",&wei[i],&val[i]); for(i=0;i<M;i++) { scanf("%d %d %d",&u,&v,&c); adj[u].pb(MP(v,c)); } pii res = rec(X,0); cout<<res.sc<<endl; Case++; } return 0;}