题解 P4473 【[国家集训队]飞飞侠】
ComplexPug · · 题解
厚颜无耻的安利一下博客
有问题可以在博客@我
既然没人发题解，那蒟蒻的我就开个头吧
清北布置的题目应该还会有人来看吧，嘻嘻
正题：
题目大意:
题目很清楚，就是一个点有一定的范围，会有一定的花费 求三个点中的任意两个点到另一个点的最小花费 (麻麻教育我千万读好题目)
思路
很容易想到跑最短路，但是建边的话，根本存不下来
所以我们直接存点的坐标，然后遍历范围内每个点就好了
每个点跑一边最短路就好了
spfa?他好像又死了(o2水过)
堆优化迪杰斯特拉是个好东西
下面是dijkstar和死了的spfa
代码：堆优化迪杰斯特拉
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
#define maxn 155
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int a[maxn][maxn];
int b[maxn][maxn];
int dis[maxn][maxn];
int x[4],y[4];
int PKU[4][4];
struct node
{
int x,y,q;
node(int xx,int yy,int qq)
{
x=xx;y=yy;
q=qq;
}
bool operator < (const node &a) const
{
return q>a.q;
}
};
inline int read()
{
int x=0,f=1;char s=getchar();
while('0'>s||s>'9') {if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9') {x=(x<<3)+(x<<1)+s-'0';s=getchar();}
return x*f;
}
void dijstra(int js)
{
memset(dis,inf,sizeof(dis));
priority_queue<node> q;
q.push(node(x[js],y[js],0));
dis[x[js]][y[js]]=0;
while(!q.empty())
{
node u=q.top();
q.pop();
if(dis[u.x][u.y]!=u.q) continue;
int len=b[u.x][u.y];
int v=dis[u.x][u.y]+a[u.x][u.y];
for(int i=max(1,u.x-len);i<=min(n,u.x+len);++i)//±éàú?ü?üè￥μ?μ?
{
int tmp=len-abs(u.x-i);
for(int j=max(1,u.y-tmp);j<=min(m,u.y+tmp);j++)
{
if(dis[i][j] > v)
{
dis[i][j] = v;
q.push(node(i,j,dis[i][j]));
}
}
}
}
for(int i=1;i<=3;++i) PKU[js][i]=dis[x[i]][y[i]];
// puts("debug:");
// for (int i = 1; i <= n; ++i)
// {
// for (int j = 1; j <= m; ++j)
// {
// cout<<dis[i][j]<<" ";
// }
// puts("");
// }
// puts("");
}
int main(int argc, char const *argv[])
{
n=read();m=read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
b[i][j]=read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j]=read();
for (int i = 1; i <= 3; ++i)
{
x[i]=read();
y[i]=read();
}
for(int i=1;i<=3;++i) dijstra(i);
int id=0,ans=inf;
for(int i=1;i<=3;++i)
{
//cout<<PKU[1][i]<<" "<<PKU[2][i]<<" "<<PKU[3][i]<<"\n";
int tm=PKU[1][i]+PKU[2][i]+PKU[3][i];
if(ans>tm) ans=tm,id=i;
}
if(ans==inf) return puts("NO"),0;
if(id==1) puts("X");
if(id==2) puts("Y");
if(id==3) puts("Z");
printf("%d",ans);
return 0;
}ps:写成了小根堆还傻傻的投诉，感觉自己好zz
代码：spfa
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
#define maxn 155
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int a[maxn][maxn];
int b[maxn][maxn];
int dis[maxn][maxn];
int vis[maxn][maxn];
int x[4],y[4];
int PKU[4][4];
struct node
{
int x,y;
node(int xx,int yy)
{
x=xx;y=yy;
}
};
inline int read()
{
int x=0,f=1;char s=getchar();
while('0'>s||s>'9') {if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9') {x=(x<<3)+(x<<1)+s-'0';s=getchar();}
return x*f;
}
void spfa(int js)
{
memset(dis,inf,sizeof(dis));
queue<node> q;
q.push(node(x[js],y[js]));
dis[x[js]][y[js]]=0;
while(!q.empty())
{
node u=q.front();
q.pop();vis[u.x][u.y]=0;
int len=b[u.x][u.y];
int v=dis[u.x][u.y]+a[u.x][u.y];
for(int i=max(1,u.x-len);i<=min(n,u.x+len);++i)//±éàú?ü?üè￥μ?μ?
{
int tmp=len-abs(u.x-i);
for(int j=max(1,u.y-tmp);j<=min(m,u.y+tmp);j++)
{
if(dis[i][j] > v)
{
dis[i][j] = v;
if(!vis[i][j])
{
vis[i][j]=1;
q.push(node(i,j));
}
}
}
}
}
for(int i=1;i<=3;++i) PKU[js][i]=dis[x[i]][y[i]];
// puts("debug:");
// for (int i = 1; i <= n; ++i)
// {
// for (int j = 1; j <= m; ++j)
// {
// cout<<dis[i][j]<<" ";
// }
// puts("");
// }
// puts("");
}
int main(int argc, char const *argv[])
{
n=read();m=read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
b[i][j]=read();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
a[i][j]=read();
for (int i = 1; i <= 3; ++i)
{
x[i]=read();
y[i]=read();
}
for(int i=1;i<=3;++i) spfa(i);
int id=0,ans=inf;
for(int i=1;i<=3;++i)
{
//cout<<PKU[1][i]<<" "<<PKU[2][i]<<" "<<PKU[3][i]<<"\n";
int tm=PKU[1][i]+PKU[2][i]+PKU[3][i];
if(ans>tm)
{
ans=tm;
id=i;
}
}
if(ans==inf)
return puts("NO"),0;
if(id==1)
puts("X");
if(id==2)
puts("Y");
if(id==3)
puts("Z");
printf("%d",ans);
return 0;
}厚颜无耻的骗波赞( • ̀ω•́ )✧