这是最短路问题和01背包问题的相结合
第一次用01背包
把j打成了i检查了半个小时 下次要注意！
使用的油耗相当于容量 而power相当于价值
先用dijkstra把从基地到所有路的最短情况算出来
然后开始01背包
所有最短路的油耗相加就是总的容量
然后开始dp【j】 算出油耗为j时能获取的最大power
大于总的power的一半时输出
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include<cstdio>
using namespace std; #define INF 0x3f3f3f3f
#define M 110 int m1[M][M];
int dis[M];
int vis[M];
int n;
int v[M]; void dijkstra()
{
memset(vis,,sizeof(vis)); for(int i=;i<=n;i++)dis[i]=INF;
dis[]=;
vis[]=;
for(int i=;i<=n;i++)
{
int minn=INF;
int u=;
for(int j=;j<=n;j++)
{
if(!vis[j]&&minn>dis[j])
{
u=j;minn=dis[j];
} }
vis[u]=;
for(int j=;j<=n;j++)
{ if(!vis[j]&&dis[u]+m1[u][j]<dis[j])
dis[j]=dis[u]+m1[u][j]; } } } int main()
{
int cas;scanf("%d",&cas);
while(cas--)
{
int m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(i==j)m1[i][j]=;
else m1[i][j]=INF;
} while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(m1[a][b]>c)m1[a][b]=m1[b][a]=c; } int sumpower=;
for(int i=;i<=n;i++)
{
int x;scanf("%d",&x);
v[i]=x;
sumpower+=x;
}
sumpower/=;
dijkstra(); int dp[]={};
memset(dp,,sizeof(dp));
int oil=;
for(int i=;i<=n;i++)
{
if(dis[i]!=INF)oil+=dis[i];
} for(int i=;i<=n;i++)
{
if(dis[i]!=INF)
{ for(int j=oil;j>=dis[i];j--)
{ dp[j]=max(dp[j],dp[ j-dis[i] ]+v[i]); }
} }
int ok=;int i;
for( i=;i<=oil;i++)
{
if(dp[i]>sumpower)
{
ok=;break;
} }
if(ok)
printf("impossible\n");
else
printf("%d\n",i); }
return ; }
回顾
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std; #define N 110
#define inf 0x3f3f3f3f
int dp[]; int n,e,m,s;
int vis[N],dis[N],mp[N][N];
int power[N]; void dijkstra(int s)
{
memset(vis,,sizeof vis);
for(int i=;i<=n;i++)dis[i]=mp[s][i];
dis[s]=; for(int i=;i<=n;i++)
{
int minn=inf,u=-; for(int j=;j<=n;j++)
if(dis[j]<minn&&!vis[j])
{
minn=dis[j];u=j;
}
if(u==-)return ;
vis[u]=;
for(int j=;j<=n;j++)
dis[j]=min(dis[j],dis[u]+mp[u][j]);
}
} int main()
{
int cas;cin>>cas;
while(cas--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(i==j)mp[i][j]=;
else mp[i][j]=inf;
}
long long oil=;
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c); if(mp[a][b]>c)mp[a][b]=mp[b][a]=c; }
int sum=;
for(int i=;i<=n;i++)
{
scanf("%d",&power[i]);
sum+=power[i];
} dijkstra();
//背包 价值为能量 容量为耗油
for(int i=;i<=n;i++)
if(dis[i]!=inf)oil+=dis[i]; memset(dp,,sizeof dp); for(int i=;i<=n;i++)
for(int j=oil;j>=dis[i];j--)
dp[j]=max(dp[j],dp[j-dis[i]]+power[i]);
sum/=;
int i;
for(i=;i<=oil;i++)
if(dp[i]>sum)
{
printf("%d\n",i);break;
}
if(i==oil+)
printf("impossible\n");
}
return ;
}