#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

最新文章

  1. href链接的地址
  2. 进击的docker 二 : docker 快速入门
  3. 数位DP HDU3652
  4. 【LeetCode 1】算法修炼 --- Two Sum
  5. java基础知识回顾之javaIO类--File类应用:删除带内容的目录
  6. http://www.ibm.com/developerworks/cn/opensource/os-cn-cas/
  7. jQuery.extend()、jQuery.fn.extend()扩展方法示例详解
  8. 使用IIS建立自己的网站、使用C#编写IIS模拟器,更好的理解Client和Server的relation
  9. Jsoup代码解读之二-DOM相关对象
  10. 设计模式 | 外观模式/门面模式(facade)
  11. EF Oracle TNS 连接
  12. 惠普笔记本fn键
  13. Linux:Day11(下) ip命令及配置文件方式
  14. HanLP 关键词提取算法分析
  15. C和C指针小记(十八)-使用结构和指针-双向链表
  16. Fernflower 反编译.class文件
  17. Kubernetes Kubelet安全认证连接Apiserver
  18. IIC总线初识
  19. [转]ORA-12560: TNS: 协议适配器错误
  20. JavaScript 获取鼠标点击位置坐标

热门文章

  1. 10 database tables
  2. (转)使用Jmeter进行http接口测试
  3. 【转载】Spark系列之运行原理和架构
  4. iOS之Photos:访问某个相册通过collectionView显示
  5. CSS重置代码和常用公共代码
  6. shell脚本中获取本机ip地址的方法
  7. Java 默认/缺省 内存大小,如果没有 -Xms -Xmx
  8. 慕课网:C++ &amp; 数据结构
  9. SAP 通过屏幕字段查看透明表
  10. 【Unity Shaders】初探Surface Shader背后的机制