各种细节坑死人
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<map> #include<cstdlib> using namespace std; const int MAXN = 110; const int INF = 1<<28; struct node { int c,sa; int node_id; }p[MAXN]; int dis[MAXN][MAXN]; int dp[MAXN][MAXN*3]; int n,m,T,s,e; void init() { int x,y,cost; scanf("%d%d%d%d%d",&n,&m,&T,&s,&e); for(int i=0;i<n;i++)scanf("%d",&p[i].c); for(int i=0;i<n;i++)scanf("%d",&p[i].sa); for(int i=0;i<n;i++)p[i].node_id = i; for(int i=0;i<n;i++)for(int j=0;j<n;j++) dis[i][j] = i==j?0:INF; for(int i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&cost); // dis[x][y] = min(dis[x][y],cost); //dis[y][x] = min(dis[y][x],cost); dis[x][y]=dis[y][x]=cost; } //memset(dp,0,sizeof(dp)); } int cmp(node a,node b) { return a.sa<b.sa; } void solve() { sort(p,p+n,cmp); for(int k=0;k<n;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) dis[i][j] = min(dis[i][j],dis[i][k]+dis[j][k]); } } for(int i=0;i<n;i++)for(int j=0;j<=T;j++)dp[i][j]=-INF; for(int i=0;i<n;i++) { dp[i][dis[s][p[i].node_id]+p[i].c] = p[i].sa; } int node_i,node_j; int oc; for(int i=0;i<n;i++) { for(int t=0;t<=T;t++) { for(int j=0;j<i;j++) { node_i = p[i].node_id; node_j = p[j].node_id; oc = t-dis[node_i][node_j]-p[i].c; if(p[i].sa > p[j].sa && oc >=0) dp[i][t] = max(dp[i][t],dp[j][oc]+p[i].sa); if(t>0) dp[i][t] = max(dp[i][t],dp[i][t-1]); } } } int ans =-INF; for(int i=0;i<n;i++) { ans = max(ans,dp[i][T-dis[p[i].node_id][e]]); } printf("%d\n",ans<0?0:ans); } int main() { freopen("4571.txt","r",stdin); int W; scanf("%d",&W); int ks = 1; while(W--) { init(); printf("Case #%d:\n",ks++); solve(); } return 0; }