黑马程序员技术交流社区

标题: 算法 [打印本页]

---

作者: 善良的禽兽    时间: 2015-9-28 22:54
标题: 算法

#include "cstdio"
#include "cmath"
#include "fstream"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define LINF 0x7f7f7f7f7f7f7f7f
#define Prime 999983
#define N 100050
using namespace std;
  
bool visited[N];
int cost[3][10];
int cc[N], cs[N];
int tcost, step;

void SPFA(int early, int goal)
{
     int cur, tmp;
     queue<int>q;
     memset(cc, 9999, sizeof(cc));
     memset(cs, 9999, sizeof(cs));
     memset(visited, true, sizeof(visited));
      
     cc[early] = cs[early] = 0;
     q.push(early); visited[early] = false;
      
     while(!q.empty())
     {
            cur = q.front(); q.pop();
           visited[cur] = true;
           
           for(int i = 0; i < 3; i++)
           {
                for(int j = 0; j < 10; j++)
                {
                      if(i == 0)
                           tmp = cur * 10 + j;
                      if(i == 1)
                           tmp = cur + j;
                      if(i == 2)
                           tmp = cur * j;
            
                      if(tmp > goal) break;
                      if(cc[tmp] > cc[cur] + cost[j])
                      {
                             cc[tmp] = cc[cur] + cost[j];
                             cs[tmp] = cs[cur] + 1;
                             if(visited[tmp])
                             {
                                   visited[tmp] = false;
                                   q.push(tmp);
                             }
                      }
                }
           }
     }
}

int main()
{
    int t(1), early, goal;
    while(~scanf("%d%d", &early, &goal))
    {
          for(int i = 0; i < 3; i++)
            for(int j = 0; j < 10; j++)
                  scanf("%d", &cost[j]);
          SPFA(early, goal);
          printf("Case %d: %d %d\n",t++, cc[goal], cs[goal]);
     
    }
    return 0;


}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2