bzoj 2143: 飞飞侠
2024-10-15 13:32:02
#include<cstdio>
#include<iostream>
#include<queue>
#define inf 1000000000
#define M 155
using namespace std;
int xx[]={,,-,,},yy[]={,,,,-};
int a[M][M],b[M][M],n,m,mx,x1,x2,y1,y2,z1,z2,a1,a2,b1,b2,c1,c2,v[M][M][*M],d[M][M][*M];
char ch;
int ans=inf;
struct data
{
int x,y,w,w1;
};
bool operator>(data a,data b)
{
return a.w>b.w;
}
void dij(int x,int y)
{
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int k=;k<=mx;k++)
{
v[i][j][k]=;
d[i][j][k]=inf;
}
priority_queue<data,vector<data>,greater<data> >q;
v[x][y][]=;
d[x][y][a[x][y]]=b[x][y];
q.push((data){x,y,b[x][y],a[x][y]});
for(;!q.empty()&&(!v[x1][x2][]||!v[y1][y2][]||!v[z1][z2][]);)
{
int x=q.top().x,y=q.top().y,w1=q.top().w1;
q.pop();
if(v[x][y][w1])
continue;
if(w1)
{
for(int i=;i<;i++)
{
int a1=x+xx[i],a2=y+yy[i];
if(a1<||a2<||a1>n||a2>m||v[a1][a2][w1-])
continue;
if(d[x][y][w1]<d[a1][a2][w1-])
{
d[a1][a2][w1-]=d[x][y][w1];
q.push((data){a1,a2,d[x][y][w1],w1-});
}
}
}
else
if(d[x][y][a[x][y]]>d[x][y][]+b[x][y])
{
d[x][y][a[x][y]]=d[x][y][]+b[x][y];
q.push((data){x,y,d[x][y][a[x][y]],a[x][y]});
}
}
for(;!q.empty();q.pop());
return;
}
int main()
{
scanf("%d%d",&n,&m);
mx=n+m-;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
a[i][j]=min(a[i][j],max(mx-i-j+,i+j-));
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&b[i][j]);
scanf("%d%d%d%d%d%d",&x1,&x2,&y1,&y2,&z1,&z2);
dij(x1,x2);
a1=d[y1][y2][];
a2=d[z1][z2][];
dij(y1,y2);
b1=d[x1][x2][];
b2=d[z1][z2][];
dij(z1,z2);
c1=d[x1][x2][];
c2=d[y1][y2][];
if(b1+c1<ans)
{
ch='X';
ans=b1+c1;
}
if(a1+c2<ans)
{
ch='Y';
ans=a1+c2;
}
if(a2+b2<ans)
{
ch='Z';
ans=a2+b2;
}
if(ans>=inf)
printf("NO");
else
printf("%c\n%d",ch,ans);
return ;
}
分层图跑DJ
最新文章
- href链接的地址
- 进击的docker 二 : docker 快速入门
- 数位DP HDU3652
- 【LeetCode 1】算法修炼 --- Two Sum
- java基础知识回顾之javaIO类--File类应用:删除带内容的目录
- http://www.ibm.com/developerworks/cn/opensource/os-cn-cas/
- jQuery.extend()、jQuery.fn.extend()扩展方法示例详解
- 使用IIS建立自己的网站、使用C#编写IIS模拟器,更好的理解Client和Server的relation
- Jsoup代码解读之二-DOM相关对象
- 设计模式 | 外观模式/门面模式(facade)
- EF Oracle TNS 连接
- 惠普笔记本fn键
- Linux:Day11(下) ip命令及配置文件方式
- HanLP 关键词提取算法分析
- C和C指针小记(十八)-使用结构和指针-双向链表
- Fernflower 反编译.class文件
- Kubernetes Kubelet安全认证连接Apiserver
- IIC总线初识
- [转]ORA-12560: TNS: 协议适配器错误
- JavaScript 获取鼠标点击位置坐标