题目链接:
http://codeforces.com/gym/100526
http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11665&courseid=0
题目大意:
一个微波炉,有N个按钮,每个按钮可以让时间加或减一个数,问达到M至少需要按几次按钮。(N<=16,0<=M<=3600)
如果无法达到M输出比M大的最小的值需要按的次数和这个值与M的差值。注意微波炉的时间满足0<=当前时间<=3600。如果超过则取边界。
题目思路:
【最短路】
初始状态d[0]=0之后按N个按钮所加的值往下扩展。每次扩展d+1.最后找d[M]和M之后第一个出现的可行解。
SPFA或BFS即可。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 // 2 //by coolxxx 3 //#include<bits/stdc++.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<string> 7 #include<iomanip> 8 #include<map> 9 #include<memory.h> 10 #include<time.h> 11 #include<stdio.h> 12 #include<stdlib.h> 13 #include<string.h> 14 //#include<stdbool.h> 15 #include<math.h> 16 #define min(a,b) ((a)<(b)?(a):(b)) 17 #define max(a,b) ((a)>(b)?(a):(b)) 18 #define abs(a) ((a)>0?(a):(-(a))) 19 #define lowbit(a) (a&(-a)) 20 #define sqr(a) ((a)*(a)) 21 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) 22 #define mem(a,b) memset(a,b,sizeof(a)) 23 #define eps (1e-8) 24 #define J 10 25 #define mod 1000000007 26 #define MAX 0x7f7f7f7f 27 #define PI 3.14159265358979323 28 #define N 24 29 #define M 3604 30 using namespace std; 31 typedef long long LL; 32 int cas,cass; 33 int n,m,lll,ans; 34 int t; 35 int b[N]; 36 int q[M],d[M]; 37 bool u[M]; 38 void spfa() 39 { 40 int i,now,to,l=0,r=1; 41 mem(d,0x7f); 42 q[1]=0;d[0]=0; 43 while(l!=r) 44 { 45 now=q[l=(l+1)%M]; 46 u[now]=0; 47 for(i=1;i<=n;i++) 48 { 49 to=now+b[i]; 50 to=max(to,0); 51 to=min(to,3600); 52 if(d[to]>d[now]) 53 { 54 d[to]=d[now]+1; 55 if(!u[to]) 56 { 57 u[to]=1; 58 q[r=(r+1)%M]=to; 59 } 60 } 61 } 62 } 63 for(i=t;i<=3600;i++) 64 if(d[i]!=MAX)break; 65 printf("%d %d ",d[i],i-t); 66 } 67 int main() 68 { 69 #ifndef ONLINE_JUDGE 70 // freopen("1.txt","r",stdin); 71 // freopen("2.txt","w",stdout); 72 #endif 73 int i,j,k; 74 int x,y,way; 75 for(scanf("%d",&cas);cas;cas--) 76 // for(scanf("%d",&cas),cass=1;cass<=cas;cass++) 77 // while(~scanf("%s",s+1)) 78 // while(~scanf("%d",&n)) 79 { 80 scanf("%d%d",&n,&t); 81 for(i=1;i<=n;i++) 82 { 83 scanf("%d",&b[i]); 84 } 85 spfa(); 86 } 87 return 0; 88 } 89 /* 90 // 91 92 // 93 */