Description

Input

Output

Sample Input

4 5 2 7 1 0 0 10 0 0 8 100 10 1 2 5 1 3 10 1 4 8 2 3 4 2 4 6

---

Sample Output

16 【样例说明】 最优方案为：先从城市1到城市2，在城市2卖掉第一颗钻石，然后到城市4，卖掉第二颗钻石并结束旅行。

---

Data Constraint

---

解题思路

分层spfa+二进制记录钻石是否买掉。 用f[i][p]表示在第i个城市，钻石情况为p时的最多剩余钱数，每到一个城市i，分别更新能去到的城市的值以及在当前城市卖钻石的值。 最后输出最大值就可以了。

---

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int N=1510; const int T=4010; const int M=1200; const int maxn=1000000; struct note { int x,y,l,ne; }; int dis[N][M],a[N][12],t[N],q[N*M],last[N]; note side[T]; int n,tt,m,k,s; void init() { memset(last,0,sizeof(last)); scanf("%d%d%d%d%d",&n,&tt,&m,&k,&s); int i,j; for (i=1;i<=n;i++) for (j=1;j<=m;j++) scanf("%d",&a[i][j]); for (i=1;i<=tt;i++) { scanf("%d%d%d",&side[i].x,&side[i].y,&side[i].l); side[i].ne=last[side[i].x]; last[side[i].x]=i; } for (i=1;i<=n;i++) for (j=0;j<=1<<(m-1);j++) dis[i][j]=-maxn; } int main() { init(); int ans=0; int i,j,l,p,head,tail; for (int d=0;d<=((1<<m)-1);d++) { tail=1; head=0; q[1]=s; dis[s][d]=k; int f=d; memset(t,0,sizeof(t)); for (int e=1;e<=m;e++) { if (f%2==1) dis[s][d]+=a[s][e]; f=f/2; } t[s]=1; for (int e=1;e<=n;e++) if (dis[e][d]!=-maxn) {tail++; q[tail]=e;} ans=k; while (head<tail) { head++; i=q[head]; l=last[i]; //printf("%d %d %d\n",i,d,dis[i][d]); ans=max(ans,dis[i][d]); while (l!=0) { p=side[l].y; if ((dis[i][d]-side[l].l>=0)&&(dis[i][d]-side[l].l>dis[p][d])) { dis[p][d]=dis[i][d]-side[l].l; if (t[p]==0) { tail++; q[tail]=p; t[p]=1; } } l=side[l].ne; } for (l=1;l<=m;l++) if ((d&(1<<(l-1)))==0) { p=d|(1<<(l-1)); //printf("%d %d %d\n",i,j,p); if (dis[i][p]<dis[i][d]+a[i][l]) dis[i][p]=dis[i][d]+a[i][l]; } t[i]=0; } } printf("%d\n",ans); return 0; }