http://blog.csdn.net/woshi250hua/article/details/7824773
题目大意：从前有n座山，山里都有一座庙，庙里都有一个老和尚，老和尚专送纪念品，每个纪念品重量为cost[i]，价值为val[i]。n座山形成一张有m条边的有向图，某山道某某山都有距离dist[i]。主角xx从st点出发，背着个容量为M的背包，想要收集最多的价值。但是主角体弱多病要顾及身体，每次背着重量为wi从某山走到某某山就要耗费dist[i]*wi的能量。最后能价值最多时最少的能量耗费为多少？
写下我的理解吧
首先我们要找到所有从x出发的通路，这个通过拓扑排序和标记来做到。
然后在这些通路中找到价值最大的:
在每个点通过之前传递的dp信息，用多重背包找出当前点价值最大，价值相等时找出精力最小
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <sstream>
using namespace std; #define mem(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define spf sprintf
#define pb push_back
#define debug printf("!\n")
#define MAXN 1010
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define pqueue priority_queue
#define INF 0x3f3f3f3f struct node
{
int v,len;
}cur; vector<node> mmap[]; int n,m,w,x; int tw[],tv[],cnt[]; int st[],result[],flag[]; long long dp[][],power[][],ans,dist; void ptopo()
{
for(int i =;i<=n;i++) pf("%d ",result[i]);
blank;
} void Debug_InPut() { for (int i = ; i <= n; ++i)
for (int j = ; j <= w; ++j)
pf("(%lld %lld)%c",dp[i][j],power[i][j],j==w?'\n':' ');
} void init()
{
ans = ;
dist = ;
memset(dp,,sizeof(dp));
memset(cnt,,sizeof(cnt));
memset(flag,,sizeof(flag));
memset(power,-,sizeof(power));
for(int i = ; i <= n; ++i)
mmap[i].clear();
} void topo()
{
int i,j;
int tot = -,index=;
for(i=;i<=n;i++)
{
if(cnt[i]==) st[++tot] = i;
//pf("%d ",st[tot]);
}
//blank;
while(tot>=)
{
int xx = st[tot--];
result[++index] = xx;
int s = mmap[xx].size();
//pf("tot%d\n",tot);
for(j=;j<s;j++)
{
cur = mmap[xx][j];
int y = cur.v;
//pf("xx%d y%d ",xx,y);
cnt[y]--;
if(cnt[y]==)
{
st[++tot] = y;
//pf("tot%d\n",tot);
//pf("y%d ",y);
}
}
}
//ptopo();
} void solve()
{
int i,j,k;
for(i=;i<=w;i++)
{
power[x][i] = ;
if(i>=tw[x])
{
dp[x][i] = max(dp[x][i],dp[x][i-tw[x]]+tv[x]);
}
if (dp[x][i] > ans)
ans = dp[x][i],dist = ;
} flag[x] = ;
for(i=;i<=n;i++)
{
int xx = result[i];
if(flag[xx]==) continue;
int s = mmap[xx].size();
for(j=;j<s;j++)
{
cur = mmap[xx][j];
int tp = cur.v;
flag[tp] = ;
for(k=;k<=w;k++)
{
if(dp[tp][k] < dp[xx][k])
{
dp[tp][k] = dp[xx][k];
power[tp][k] = power[xx][k] + cur.len*k;
}
else if(dp[tp][k] == dp[xx][k])
{
if(power[tp][k] == -)
{
power[tp][k] = power[xx][k]+cur.len * k;
}
else
power[tp][k] = min(power[xx][k] + cur.len*k ,power[tp][k]);
}
} for (k = tw[tp]; k <= w; ++k) {
//完全背包
if (dp[tp][k] < dp[tp][k-tw[tp]]+tv[tp]) {
dp[tp][k] = dp[tp][k-tw[tp]] + tv[tp];
power[tp][k] = power[tp][k-tw[tp]];
}
else if(dp[tp][k] == dp[tp][k-tw[tp]]+tv[tp])
power[tp][k] = min(power[tp][k],power[tp][k-tw[tp]]);
} for (k = ; k <= w; ++k) {
//更新答案
if (dp[tp][k] > ans)
ans = dp[tp][k],dist = power[tp][k];
else if (dp[tp][k] == ans)
dist = min(dist,power[tp][k]);
}
//pf("cur %d:\n",cur.v),Debug_InPut();
}
}
} int main()
{
int i,j;
while(~sf("%d%d%d%d",&n,&m,&w,&x))
{
init(); for(i=;i<=n;i++) sf("%d%d",&tw[i],&tv[i]); for(i=;i<m;i++)
{
int x,y,l;
sf("%d%d%d",&x,&y,&l);
cur.v = y;
cur.len = l;
cnt[y]++;
mmap[x].pb(cur);
}
topo();
solve();
//pf("ans %lld %lld\n",ans,dist);
printf("%lld\n",dist);
}
return ;
}