bzoj千题计划225:bzoj2143: 飞飞侠

http://www.lydsy.com/JudgeOnline/problem.php?id=2143

分层图最短路

把能够弹跳的曼哈顿距离看做能量

dp[i][j][k]表示在(i,j)位置,还有能量k的最少花费

弹跳的曼哈顿距离增加1,能量减1

当能量减为0时,花费费用充满能量

#include<queue>
#include<cstdio>
#include<iostream> #define N 151 typedef long long LL; const LL inf=1e17; using namespace std; int n,m;
int energy[N][N],cost[N][N]; int X[],Y[]; LL dp[N][N][N<<];
bool vis[N][N][N<<]; int dx[]={,-,,,};
int dy[]={,,,,-}; struct node
{
int x,y,k;
LL val; node(int x_=,int y_=,int k_=,int val_=) :x(x_),y(y_),k(k_),val(val_) {} bool operator < (node p) const
{
return val>p.val;
} }now; priority_queue<node>q; void read(int &x)
{
x=; int f=; char c=getchar();
while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
x*=f;
} void dijkstra(int e)
{
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
for(int k=;k<=n+m-;++k)
{
dp[i][j][k]=inf;
vis[i][j][k]=false;
}
while(!q.empty()) q.pop();
vis[X[e]][Y[e]][]=true;
dp[X[e]][Y[e]][energy[X[e]][Y[e]]]=cost[X[e]][Y[e]];
now.x=X[e];
now.y=Y[e];
now.k=energy[now.x][now.y];
now.val=cost[now.x][now.y];
q.push(now);
int sx,sy,nx,ny,k;
while(!q.empty() && (!vis[X[]][Y[]][] || !vis[X[]][Y[]][] || !vis[X[]][Y[]][]))
{
now=q.top();
q.pop();
sx=now.x; sy=now.y; k=now.k;
if(vis[sx][sy][k]) continue;
vis[sx][sy][k]=true;
if(now.k)
{
for(int i=;i<;++i)
{
nx=now.x+dx[i];
ny=now.y+dy[i];
if(nx<= || nx>n || ny<= || ny>m) continue;
if(dp[sx][sy][k]<dp[nx][ny][k-])
{
dp[nx][ny][k-]=dp[sx][sy][k];
q.push(node(nx,ny,k-,dp[nx][ny][k-]));
}
}
}
else
{
if(dp[sx][sy][]+cost[sx][sy]<dp[sx][sy][energy[sx][sy]])
{
dp[sx][sy][energy[sx][sy]]=dp[sx][sy][]+cost[sx][sy];
q.push(node(sx,sy,energy[sx][sy],dp[sx][sy][energy[sx][sy]]));
}
}
}
} int main()
{
int x;
read(n); read(m);
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
{
read(x);
energy[i][j]=min(x,max(i-,n-i)+max(j-,m-j));
}
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
read(cost[i][j]);
for(int i=;i<=;++i)
read(X[i]),read(Y[i]);
LL ans=inf; char pos;
dijkstra();
LL a1=dp[X[]][Y[]][],a2=dp[X[]][Y[]][];
dijkstra();
LL b1=dp[X[]][Y[]][],b2=dp[X[]][Y[]][];
dijkstra();
LL c1=dp[X[]][Y[]][],c2=dp[X[]][Y[]][];
if(b1+c1<ans) ans=b1+c1,pos='X';
if(a1+c2<ans) ans=a1+c2,pos='Y';
if(a2+b2<ans) ans=a2+b2,pos='Z';
if(ans>=inf) printf("NO");
else printf("%c\n%lld",pos,ans);
return ;
}
上一篇:Java获取指定时间的毫秒值的方法


下一篇:【原创】windows下搭建vue开发环境+IIS部署