原题from: ACPC 2013
题意:有n个车站,编上不同的号,M个硬币,费用为cost,价值为val, 每次移动的最高花费L,问从最小编号的车站到最大编号最少要移动多少次。每次移动(i-->j)从M中选择一些硬币(每次移动硬币只能选一次)使得价值正好等于 j-i。
思路:先0-1背包求出i-->j的最少花费,注意是要装满背包,然后建图,若i->j费用<=L,则有边,所有边权值为1,最后求个最短路
code:
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <iomanip> #include <queue> #include <vector> #include <set> #include <map> #define LL long long #define inf 0x3f3f3f3f #define P system("pause") using namespace std; #define M 105 int cost[105],val[105],n,m,L; int p[105],g[M][M],dp[1005],dis[M],vis[M]; void DP()//背包 { for(int i=0;i<1005;i++) dp[i]=inf; dp[0]=0; for(int i=0;i<m;i++) { for(int j=p[n-1]-p[0];j>=val[i];j--) dp[j]=min(dp[j],dp[j-val[i]]+cost[i]); } } void build()//建图 { for(int i=0;i<n;i++) for(int j=0;j<n;j++) g[i][j]=(p[i]==p[j])?0:inf; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(dp[p[j]-p[i]]<=L){ g[i][j]=g[j][i]=1; //cout<<p[i]<<"->"<<p[j]<<endl; } } } } int dij(int u)//dijskstra求最短路 { int i,j,v; memset(vis,0,sizeof(vis)); for(i=0;i<n;i++) dis[i]=g[u][i]; dis[u]=0; vis[u]=1; for(i=1;i<n;i++) { int mi=inf,v=u; for(j=0;j<n;j++) { if(!vis[j]&&dis[j]<mi){ mi=dis[j]; v=j; } } vis[v]=1; for(j=0;j<n;j++) { if(!vis[j]&&dis[j]>dis[v]+g[v][j]) dis[j]=dis[v]+g[v][j]; } } int ans=dis[n-1]; if(ans==inf) return -1; return ans; } int main() { int t,i; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&L); for(i=0;i<n;i++) scanf("%d",&p[i]); for(i=0;i<m;i++) scanf("%d%d",&cost[i],&val[i]); sort(p,p+n); DP(); build(); printf("%d\n",dij(0)); } return 0; }