C++(g++ 7.5.0) 解法, 执行用时: 242ms, 内存消耗: 6800K, 提交时间: 2023-07-24 22:52:16

#include<iostream>
#include<queue>
using namespace std;
const int N = 505;
typedef long long ll;

struct node {
	int x, y;
	ll w;
	bool operator<(const node& x) const {
		return w > x.w;
	}
};

int n, m, t;
int way[4][2] = { -1,0,1,0,0,-1,0,1 };
ll v[N][N];
bool st[N][N];

int main()
{
	cin >> t >> n >> m;
	while (t--) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cin >> v[i][j];
				if (v[i][j] == -1) v[i][j] = 0;
				else if (v[i][j] == 0) v[i][j] = 1e18;
				st[i][j] = false;
			}
		}

		priority_queue<node> que;
		for (int i = 2; i <= n; i++) if (v[i][m] != 1e18) que.push({ i,m,v[i][m] });
		for (int j = 2; j <= m; j++) if (v[1][j] != 1e18) que.push({ 1,j,v[1][j] });
		
		ll res = 1e18;
		while (que.size()) {
			auto s = que.top();
			que.pop();
			int x = s.x, y = s.y;
			ll w = s.w;

			if (x == n || y == 1) {
				res = min(res, w);
				continue;
			}
			if (st[x][y]) continue;
			st[x][y] = true;

			for (int i = 0; i < 4; i++) {
				int xi = x + way[i][0];
				int yi = y + way[i][1];
				if (xi<1 || xi>n || yi<1 || yi>m || v[xi][yi] == 1e18) continue;
				que.push({ xi,yi,w + v[xi][yi] });
			}
			
		}
		if (res == 1e18) cout << -1 << endl;
		else cout << res << endl;
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 131ms, 内存消耗: 6512K, 提交时间: 2018-10-19 21:54:05

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL;
const int N = 505;
const int go[4][2]= {0,1,1,0,0,-1,-1,0};
const LL inf = (1LL << 60) - 1;
struct node{
	LL dis;
	int x,y;
	bool operator < (const node &t) const {
		return dis > t.dis;
	}
};
LL a[N][N],dis[N][N];
int main() {
	int n,m,q;
	scanf("%d %d %d",&q,&n,&m);
	while(q--) {
		rep(i,1,n) {
			rep(j,1,m) {
				scanf("%lld",&a[i][j]);
				if(a[i][j] == 0) {
					a[i][j] = inf;
				}
				if(a[i][j] == -1) {
					a[i][j] = 0;
				}
				dis[i][j] = inf;
			}
		}
		priority_queue<node> q;
		rep(i,2,n-1) {
			dis[i][1] = a[i][1];
			q.push({dis[i][1],i,1});
		}
		rep(j,1,m-1) {
			dis[n][j] = a[n][j];
			q.push({dis[n][j],n,j});
		}
		while(!q.empty()) {
			node t = q.top();
				     q.pop();
			rep(i,0,4) {
				int dx = t.x + go[i][0];
				int dy = t.y + go[i][1];
				if(dx >= 1 && dx <= n && dy >= 1 && dy <= m) {
					if(dis[dx][dy] > dis[t.x][t.y] + a[dx][dy]) {
						dis[dx][dy] = dis[t.x][t.y] + a[dx][dy];
						q.push({dis[dx][dy],dx,dy});
					}
				}
			}
		}
		LL res = inf;
		rep(i,1,n-1) res = min(res,dis[i][m]);
		rep(j,2,m-1) res = min(res,dis[1][j]);
		printf("%lld\n",res >= inf ? -1 : res);
	}
}

C++ 解法, 执行用时: 254ms, 内存消耗: 8624K, 提交时间: 2022-02-02 22:43:52

#include<bits/stdc++.h>
using namespace std;
const int N=510;
#define ll long long
int n,m,dir[4][2]={-1,0,1,0,0,1,0,-1};
ll mp[N][N],vis[N][N];
ll res;
struct ty
{
	int x,y;
	ll dis;
	bool operator<(const ty &k)const
	{
		return dis>k.dis;
	}
};
priority_queue<ty>q;
void dij()
{
	while(!q.empty())
	{
		ty nxt=q.top();
		q.pop();
		int x=nxt.x;
		int y=nxt.y;
		ll dis=nxt.dis;
		if(y==1||x==n)
		{
			res=min(res,dis);
			continue;
		}
		if(vis[x][y])continue;
		vis[x][y]=1;
		for(int i=0;i<4;i++)
		{
			int tx=x+dir[i][0];
			int ty=y+dir[i][1];
			if(tx<1||tx>n||ty>m||ty<1||mp[x][y]==1e18)continue;
			q.push({tx,ty,dis+mp[tx][ty]});
		}
	}
}
int main()
{
	int T;
	cin>>T>>n>>m;
	while(T--)
	{
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>mp[i][j];
			if(mp[i][j]==0)mp[i][j]=1e18;
			else if(mp[i][j]==-1)mp[i][j]=0;
			vis[i][j]=0;
		}
		for(int j=2;j<=m;j++)
		if(mp[1][j]!=1e18)q.push({1,j,mp[1][j]});
		for(int i=2;i<n;i++)
		if(mp[i][m]!=1e18)q.push({i,m,mp[i][m]});
		res=1e18;
		dij();
		if(res==1e18)cout<<-1<<endl;
		else cout<<res<<endl;
	}
	return 0;
}