不知道为什么就错了好几个点,查了一晚上也没查出来
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n,k,a_,b_,c_;
int n_;
int c[105][105];
vector<vector<int>> e,w;
inline int id(int i,int j,int k)
{
return ((i-1)*n+j)+k*(n*n);
}
class graph
{
template <class type>
struct node
{
int id;
type dis;
bool operator < (node other) const
{
return this->dis>other.dis;
}
};
public:
const long long inf=0x3f3f3f3f;
template <class type>
type dij(int n,int l,vector<vector<type>>e,vector<vector<type>>w)
{
type dis[n+5];
for(int i=1;i<=n;i++)
dis[i]=inf;
dis[l]=0;
bool vis[n+5]={};
priority_queue<node<type>>q;
node<type>temp;
temp.id=l;
temp.dis=0;
q.push(temp);
while(q.size()!=0)
{
int t=q.top().id;
q.pop();
if(vis[t])
continue;
vis[t]=true;
for(int i=0;i<e[t].size();i++)
{
int u=e[t][i];
if(dis[u]>dis[t]+w[t][i])
{
dis[u]=dis[t]+w[t][i];
node<type>next;
next.id=u;
next.dis=dis[u];
q.push(next);
}
}
}
vector<type>ans;
ans.push_back(0);
for(int i=1;i<=n;i++)
ans.push_back(dis[i]);
int f=0x3f3f3f3f3f;
for(int i=0;i<=k;i++)
f=min(f,dis[id(n_,n_,i)]);
return f;
}
};
template <class type>
type dij(int n,int l,vector<vector<type>>e,vector<vector<type>>w)
{
graph g;
return g.dij(n,l,e,w);
}
inline void to_id(int num,int &i,int &j,int &k)
{
j=num%n;
if(j==0)
j=n;
k=num/(n*n);
if(num%(n*n)==0)
k--;
int id=num%(n*n);
if(id==0)
id=n*n;
i=id/n+1;
if(id%n==0)
i--;
}
inline void add(int u,int v,int s)
{
e[u].push_back(v);
w[u].push_back(s);
}
inline bool safe(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=n;
}
int main()
{
cin>>n>>k>>a_>>b_>>c_;
e.resize(150005);
w.resize(150005);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>c[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int l=0;l<=k;l++)//还剩l格油
{
int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
for(int s=1;s<=4;s++)
if(safe(i+dx[s],j+dy[s]))
{
//下一个位置
int nx=i+dx[s],ny=j+dy[s];
//记录费用
int money=0;
//加油站费用
if(l==0&&c[i][j]==1)
{
money+=a_;
}
else
{
if(l==0)
money+=c_+a_;
}
if(c[nx][ny]==1)
money+=a_;
if(s==2||s==4)
money+=b_;
int nl;//转移出来是哪一层
if(l==0)
nl=k;
else if(c[nx][ny]==1)
nl=k;
else
nl=l-1;
add(id(i,j,l),id(nx,ny,nl),money);
}
}
n_=n;
cout<<dij(n*n+k*n*n,id(1,1,k),e,w);
return 0;
}