题意：
给定6个硬币的币值， 问组成1~100这些数最少要几个硬币， 比如给定1 2 5 10 20 50， 组成40 可以是 20 + 20， 也可以是 50 -10， 最少硬币是2个。
分析：
这道题可以转化成是一道最短路的方法去做， 设一开始的起点为0（什么硬币都不取）， 然后每个点都有12条路（对应正负6种币值）， 每条路的权值为1，
令dis[maxn]初始化为inf, 求出dis[1]~dis[100]即可。
但是最大值maxn要取比100更大， 比如 构造100的最优方法为51+51-1-1. 那么我们就需要102面值金钱的构造dist[102] 才能正确的推出dist[100], 虽然不知道这个最大值多少，但这个最大值取200可以过这题。
1 #include <cstdio> 2 #include <iostream> 3 #include <queue> 4 #include <cstring> 5 #define mem(a) memset(a, 0, sizeof(a)) 6 using namespace std; 7 const int maxn = 207; 8 const int inf = 1e9; 9 int coin[12]; 10 int dis[maxn]; 11 int vis[maxn]; 12 void spfa(){ 13 mem(vis); 14 queue<int> q; 15 fill(dis,dis+maxn, inf); 16 dis[0] = 0; 17 vis[0] = 1; 18 q.push(0); 19 while(!q.empty()){ 20 int u = q.front(); 21 for(int i = 0; i < 12; i++){ 22 int v = u + coin[i]; 23 if(v < 0 || v > 200) continue;//如果点v是负数， 那么不需要入队。 24 if(dis[v] > dis[u] + 1){ 25 dis[v] = dis[u] + 1; 26 if(!vis[v]){ 27 vis[v] = 1; 28 q.push(v); 29 } 30 } 31 } 32 // vis[u] = 0; 这里其实不用标记， 因为每个点只会入队一次，边的权值都是1， 怎么扩展都是最短路 33 q.pop(); 34 } 35 } 36 int main() 37 { 38 int t; 39 cin >> t; 40 while ( t -- ) { 41 for ( int i = 0 ; i < 6 ; ++ i ){ 42 cin >> coin[ 2*i ]; 43 coin[2 * i + 1] = -coin[2 * i];//构造币值为负数的硬币 44 } 45 spfa(); 46 double sum = 0.0; 47 int maxdis = 0; 48 for ( int i = 1 ; i <= 100 ; ++ i ) { 49 sum += dis [i]; 50 if ( dis[i] > maxdis ) 51 maxdis = dis[i]; 52 } 53 printf("%.2f %d ",sum/100.0, maxdis); 54 } 55 return 0; 56 }