-
题目大意
这是一个关于二维格子状迷宫的题目。迷宫的大小为N*M，左上角格子座标为(1,1)、右上角格子座标为(1,M)、左下角格子座标为(N,1)、右下角格子座标为(N,M)。每一格都用-1到109之间的整数表示，意义分别为：-1为墙壁，0为走道，而1到109之间的正整数代表特殊的走道。
蜥蜴最初位于迷宫的座标(1,1)的格子，每一步蜥蜴只能往上、下、左、右、左上、右上、左下、右下八个方向之一前进一格，并且，他也不能走出迷宫边界。蜥蜴的目的地是走到迷宫的右下角格子，也就是座标位置(N,M)。我们想要动一些手脚，使得蜥蜴没有办法从(1,1)出发并抵达(N,M)。我们学会了一个邪恶的法术，这个法术可以把特殊的走道变成墙壁，施法一次的代价为表示该特殊走道的正整数。
假设，我们可以在蜥蜴出发之前不限次数的使用这个邪恶的法术，所花的总代价即为每次施法代价的总和，蜥蜴出发之后就不能再使用这个法术了，请问让蜥蜴没办法达到终点所必须花费的最小总代价是多少呢？
注意，0所代表的走道是无法变为墙壁的。 -
分析
实质上就是建造一面墙壁，且建造的墙壁的代价最小。
墙壁有四种分布情况
1.墙壁的一头在左边界，另一头在上边界。
2.墙壁的一头在左边界，另一头在右边界。
3.墙壁的一头在下边界，另一头在上边界。
4.墙壁的一头在下边界，另一头在右边界。
我们要做的就是给位于的左边界点添加一个源点，给下边界的点添加一个源点，从两个源点出发跑一个最短路就可以了。 -
错误分析
刚开始写的时候认为只要到边界了，那这个时候构筑的墙壁就是代价最小的，直接返回这个值，实际上这是不正确的，后面的点可能更新出更小的答案，所以是在到达边界的点中选取最小值。另一种操作是把上右边界的点都增加边抵达一个新源点，最后只需要返回到这个源点的距离即可。
另一个错误是我把两个源点分别跑了一遍最短路，导致的结果就是超时，实际上可以把这两个源点同时入队，跑一遍最短路。本质上等于给这两个源点又增添了一个到这两个源点代价为0的源点。从此源点出发跑最短路。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct ty1{
ll sx,sy;
ll nx,ny;
ll len;
ll next;
}edge[4000000];
struct ty2{
ll x,y;
ll v;
};
ll head[510][510];
ll cnt;
ll dis[510][510];
ll mp[510][510];
ll vis[510][510];
ll n,m;
ll t;
int read()
{
int x=0;
int flag=1;
char c=getchar();
while(c!='-'&&!(c>='0'&&c<='9'))c=getchar();
if(c=='-')flag=-1;
else x=c-'0';
c=getchar();
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*flag;
}
void add(ll x1,ll y1,ll x2,ll y2){
edge[++cnt].sx = x1;
edge[cnt].sy = y1;
edge[cnt].nx = x2;
edge[cnt].ny = y2;
if(mp[x2][y2]!=-1)//-1点的代价不计
edge[cnt].len = mp[x2][y2];
else
edge[cnt].len = 0;
edge[cnt].next = head[x1][y1];
head[x1][y1] = cnt;
}
bool operator<(const ty2 &a,const ty2 &b){
return a.v>b.v;
}
ll res;
priority_queue<ty2> q;
ll dij(){
q.push({501,501,0});
q.push({502,502,0});
while(!q.empty()){
auto front = q.top();
// cout<<front.v<<endl;
q.pop();
ll xx = front.x;
ll yy = front.y;
// cout<<xx<<" "<<yy<<endl;
if(xx == 1||yy==m) {
// cout<<xx<<" "<<yy<<" "<<front.v<<endl;
res = min(res,front.v);
continue;
}
if(vis[xx][yy]||(mp[xx][yy]==0&&xx!=501&&xx!=502)) continue;
vis[xx][yy] = 1;
for(ll i = head[xx][yy];i!=-1;i = edge[i].next){
//cout<<i<<endl;
ll kx = edge[i].nx;
ll ky = edge[i].ny;
if(!vis[kx][ky]&&edge[i].len+dis[xx][yy]<dis[kx][ky]&&mp[kx][ky]!=0){
//0的格子不能变为墙壁
// cout<<xx<<" "<<yy<<" "<<kx<<" "<<ky<<" "<<dis[kx][ky]<<" "<<edge[i].len+dis[xx][yy]<<endl;
dis[kx][ky] = edge[i].len+dis[xx][yy];
q.push({kx,ky,dis[kx][ky]});
}
}
}
return -1;
}
ll dx[9] = {1,0,-1,0};
ll dy[9] = {0,1,0,-1};
int main(){
t = read();
n = read();
m = read();
while(t--){
res = 2e18;
while(!q.empty()) q.pop();
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
dis[i][j] = 2e18;
}
}
cnt = 0;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
mp[i][j] = read();
}
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
for(int k = 0;k<=3;k++){
ll px = i+dx[k];
ll py = j+dy[k];
if(px<1||px>n||py<1||py>m) continue;
add(i,j,px,py);
}
}
}
for(int i = 2;i<=n;i++){
add(501,501,i,1);
}
for(int i = 1;i<=m-1;i++){
add(502,502,n,i);
}
mp[501][501] = 0;
dis[501][501] = 0;
mp[502][502] = 0;
dis[502][502] = 0;
dij();
if(res==2e18) cout<<-1<<endl;
else cout<<res<<endl;
}
}