题目链接：https://cn.vjudge.net/contest/245287#problem/I
代码：
使用普通的队列和优先队列相比，优先队列能更快地找到目的变量。
#include<iostream>
#include<string>
#include<cstring>
#include<iomanip>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
# define inf 0x3f3f3f3f
const int maxn=1e8+10;
int n,m;
int a[104][105];
int cost[maxn];
struct node
{
int cost;
int step;
int mon;
node() {}
node(int xx,int yy,int zz)
{
cost=xx;
step=yy;
mon=zz;
}
friend bool operator < (node a,node b)
{
if(a.cost>b.cost)return true;
else if(a.cost==b.cost&&a.step>b.step)return true;
return false;
}
} temp1,temp;
void bfs()
{
memset(cost,inf,sizeof(cost));
priority_queue<node>q;
cost[n]=0;
q.push(node(0,0,n));
while(!q.empty())
{
temp=q.top();
q.pop();
if(temp.mon==m)
{
cout<<temp.cost<<" "<<temp.step<<endl;
return ;
}
for(int i=1; i<=3; i++)
{
for(int j=1; j<=10; j++)
{
if(i==1)
{
temp1.cost=temp.cost+a[i][j];
temp1.mon=temp.mon*10+j-1;
temp1.step=temp.step+1;
}
if(i==2)
{
temp1.cost=temp.cost+a[i][j];
temp1.mon=temp.mon+j-1;
temp1.step=temp.step+1;
}
if(i==3)
{
temp1.cost=temp.cost+a[i][j];
temp1.mon=temp.mon*(j-1);
temp1.step=temp.step+1;
}
if(temp1.mon<=m&&cost[temp1.mon]>temp1.cost)
{
cost[temp1.mon]=temp1.cost;
q.push(temp1);
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
int s=1;
while(cin>>n>>m)
{
for(int i=1; i<=3; i++)
{
for(int j=1; j<=10; j++)
{
cin>>a[i][j];
}
}
cout<<"Case "<<s++<<": ";
bfs();
}
return 0;
}