「BZOJ2143」飞飞侠

2014年10月23日6,4562

Description

飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵，每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么，任何飞飞侠都只需要在(i,j)支付Aij的费用就可以任意选择弹到距离不超过Bij的位置了。如下图（从红色街区交费以后可以跳到周围的任意蓝色街区。）现在的问题很简单。有三个飞飞侠，分别叫做X，Y，Z。现在它们决定聚在一起玩，于是想往其中一人的位置集合。告诉你3个飞飞侠的坐标，求往哪里集合大家需要花的费用总和最低。

Input

输入的第一行包含两个整数N和M，分别表示行数和列数。接下来是2个N×M的自然数矩阵，为Aij和Bij 最后一行六个数，分别代表X，Y，Z所在地的行号和列号。

Output

第一行输出一个字符X、Y或者Z。表示最优集合地点。第二行输出一个整数，表示最小费用。如果无法集合，只输出一行NO

Sample Input

4 4
0 0 0 0
1 2 2 0
0 2 2 1
0 0 0 0
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5
2 1 3 4 2 2

Sample Output

Z
15
「范围」
100% 1 < = N, M < = 150; 0 < = Bij < = 109; 0 < = Aij < = 1000

题解

这道题点很少，但是边可能很多，直接建图做最短路显然不可行

但是如果把弹射看成获得了可以走a[i][j]的能量

这样就可以直接最短路了

每走一格消耗1的能量，f[i][j][k]表示在i，j这个点且有k的能量的最少费用

每次只要向四个方向走，或者原地不动即可

做三次最短路

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define ll long long
#define inf 1000000000
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char ans;int mn=inf;
int xx[5]={0,0,1,-1,0},yy[5]={1,-1,0,0,0};
int a1,a2,b1,b2,c1,c2;
int n,m,mx;
int x1,y1,x2,y2,x3,y3;
int a[155][155],b[155][155];
int d[155][155][305];
bool vis[155][155][305];
struct data{int w,x,y,s;};
bool operator>(data a,data b)
{
    return a.w>b.w;
}
void dij(int x,int y)
{
    priority_queue<data,vector<data>,greater<data> > q;
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<=mx;k++)
			{
				vis[i][j][k]=0;
				d[i][j][k]=inf;
			}
    vis[x][y][0]=1;
    d[x][y][a[x][y]]=b[x][y];
    q.push((data){b[x][y],x,y,a[x][y]});
    while(!q.empty()&&(!vis[x1][y1][0]||!vis[x2][y2][0]||!vis[x3][y3][0]))
    {
		int x=q.top().x,y=q.top().y,s=q.top().s;q.pop();
		if(vis[x][y][s])continue;vis[x][y][s]=1;
		if(s>0)
		{
			for(int k=0;k<5;k++)
			{
				int nowx=x+xx[k],nowy=y+yy[k];
				if(nowx<1||nowy<1||nowx>n||nowy>m||vis[nowx][nowy][s-1])continue;
				if(d[x][y][s]<d[nowx][nowy][s-1])
				{
					d[nowx][nowy][s-1]=d[x][y][s];
					q.push((data){d[nowx][nowy][s-1],nowx,nowy,s-1});
				}
			}
		}
		else
		{
			int t=a[x][y];
			if(d[x][y][t]>d[x][y][0]+b[x][y])
			{
				d[x][y][t]=d[x][y][0]+b[x][y];
				q.push((data){d[x][y][t],x,y,t});
			}
		}
    }
    while(!q.empty())q.pop();
}
int main()
{   
    n=read();m=read();mx=n+m-2;
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			a[i][j]=read();
			a[i][j]=min(a[i][j],max(mx-i-j,i+j-2));
		}
    for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			b[i][j]=read();
    x1=read();y1=read();x2=read();y2=read();x3=read();y3=read();
    dij(x1,y1);a1=d[x2][y2][0];a2=d[x3][y3][0];
    dij(x2,y2);b1=d[x1][y1][0];b2=d[x3][y3][0];
    dij(x3,y3);c1=d[x1][y1][0];c2=d[x2][y2][0];
    if(b1+c1<mn)mn=b1+c1,ans='X'; 
    if(a1+c2<mn)mn=a1+c2,ans='Y';
    if(a2+b2<mn)mn=a2+b2,ans='Z';
    if(mn==inf)puts("NO");
    else
    {
        printf("%c\n",ans);
        printf("%d\n",mn);
    }
    return 0;
}

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<queue>

#define ll long long

#define inf 1000000000

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

char ans;int mn=inf;

int xx[5]={0,0,1,-1,0},yy[5]={1,-1,0,0,0};

int a1,a2,b1,b2,c1,c2;

int n,m,mx;

int x1,y1,x2,y2,x3,y3;

int a[155][155],b[155][155];

int d[155][155][305];

bool vis[155][155][305];

struct data{int w,x,y,s;};

bool operator>(data a,data b)

{

return a.w>b.w;

}

void dij(int x,int y)

{

priority_queue<data,vector<data>,greater<data> > q;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

for(int k=0;k<=mx;k++)

{

vis[i][j][k]=0;

d[i][j][k]=inf;

}

vis[x][y][0]=1;

d[x][y][a[x][y]]=b[x][y];

q.push((data){b[x][y],x,y,a[x][y]});

while(!q.empty()&&(!vis[x1][y1][0]||!vis[x2][y2][0]||!vis[x3][y3][0]))

{

int x=q.top().x,y=q.top().y,s=q.top().s;q.pop();

if(vis[x][y][s])continue;vis[x][y][s]=1;

if(s>0)

{

for(int k=0;k<5;k++)

{

int nowx=x+xx[k],nowy=y+yy[k];

if(nowx<1||nowy<1||nowx>n||nowy>m||vis[nowx][nowy][s-1])continue;

if(d[x][y][s]<d[nowx][nowy][s-1])

{

d[nowx][nowy][s-1]=d[x][y][s];

q.push((data){d[nowx][nowy][s-1],nowx,nowy,s-1});

}

else

{

int t=a[x][y];

if(d[x][y][t]>d[x][y][0]+b[x][y])

{

d[x][y][t]=d[x][y][0]+b[x][y];

q.push((data){d[x][y][t],x,y,t});

}

while(!q.empty())q.pop();

}

int main()

{

n=read();m=read();mx=n+m-2;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

{

a[i][j]=read();

a[i][j]=min(a[i][j],max(mx-i-j,i+j-2));

}

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

b[i][j]=read();

x1=read();y1=read();x2=read();y2=read();x3=read();y3=read();

dij(x1,y1);a1=d[x2][y2][0];a2=d[x3][y3][0];

dij(x2,y2);b1=d[x1][y1][0];b2=d[x3][y3][0];

dij(x3,y3);c1=d[x1][y1][0];c2=d[x2][y2][0];

if(b1+c1<mn)mn=b1+c1,ans='X';

if(a1+c2<mn)mn=a1+c2,ans='Y';

if(a2+b2<mn)mn=a2+b2,ans='Z';

if(mn==inf)puts("NO");

else

{

printf("%c\n",ans);

printf("%d\n",mn);

}

return 0;

}

« 「CF480B」Long Jumps 「BZOJ2709」[Violet 1] 迷宫花园 »

Paul White

ORZ

zdy

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
a[i][j]=read();
a[i][j]=min(a[i][j],max(mx-i-j,i+j-2));
}
这一段好像判错了吧。。应该是a[i][j]=min(a[i][j],mx);否则应该判四个点。。。
（scar_lyw改我代码时发现的）

hzwer.com _ Home | http://hzwer.com

「BZOJ2143」飞飞侠

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论