hdoj3339——最短路+01背包

最短路+01背包,但还没完全想清楚。
在装入背包时是否有可能出现装入最优方案时impossible,但是选择一种次优方案却可以得到值?

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1000
#define maxe 10000000
#define inf 1000010
using namespace std;
typedef struct node{
	int dist,point;
	bool operator < (const node& a) const
	{
		return dist>a.dist;
	}
}node;
typedef struct Edge{
	int w;
	int to;
	int next;
}Edge;
int head[maxn];
Edge edge[maxe];
int dist[maxn],pre[maxn];
bool visit[maxn];
int n,m;
void dij(int s)
{
	int i;
	priority_queue<node> q;
	for(i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	memset(visit,0,sizeof(visit));
	node sr;
	sr.dist=0;sr.point=s;
	q.push(sr);
	while(!q.empty())
	{
		node x=q.top();q.pop();
		int u=x.point;
		if(visit[u]) continue;
		visit[u]=1;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].w)
			{
				dist[v]=dist[u]+edge[i].w;
				pre[v]=u;
				node tmp;
				tmp.dist=dist[v];tmp.point=v;
				q.push(tmp);
			
			}
		}
	}
	return;
}
int max(int a,int b)
{
	return a>b?a:b;
}
int dp[6000];
int main()
{
	int t;
	int i,j;
	scanf("%d",&t);
	while(t--)
	{
		int cnt=0;
		memset(head,-1,sizeof(head));
		scanf("%d %d",&n,&m);
		n++;
		int a,b,w;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&w);
			a++;
			b++;
			edge[cnt].to=b;
			edge[cnt].w=w;
			edge[cnt].next=head[a];
			head[a]=cnt++;

			edge[cnt].to=a;
			edge[cnt].w=w;
			edge[cnt].next=head[b];
			head[b]=cnt++;
		}
		int pow[maxn];
		int V=0;
		for(i=1;i<=n-1;i++)
		{
			scanf("%d",&pow[i]);
			V+=pow[i];
		}
		dij(1);
		int len=0;
		for(i=2;i<=n;i++)
		{
			len+=dist[i];
			dist[i-1]=dist[i];
		}
		if(V&1)
			V/=2;
		else
			V=V/2-1;
		for(j=0;j<=V;j++)
			dp[j]=0;
		for(i=1;i<=n-1;i++)
			for(j=V;j>=0;j--)
			{
				if(j>=pow[i])
				{
					dp[j]=max(dp[j],dp[j-pow[i]]+dist[i]);
				
				}
			}
			int ans=len-dp[V];
			if(ans>=inf)
				printf("impossible\n");
			else
				printf("%d\n",ans);

		




		
	
	
	
	
	}

system("pause");
return 0;
}