56pts 最短路 求助
查看原帖
56pts 最短路 求助
572133
潘德理2010楼主2023/12/16 18:49
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,z,n,d[40][40],c[40][40];
ll x[10]={0,1,1,-1,-1,2,2,-2,-2},y[10]={0,2,-2,2,-2,1,-1,1,-1};
ll dis[1000],val[1000],vis[1000],st,en;
vector<pair<ll,ll> > e[1000];
priority_queue<pair<ll,ll> ,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
int main(){
	scanf("%lld%lld",&a,&b);
	for(ll i=1;i<=a;i++){
		for(ll j=1;j<=b;j++){
			c[i][j]=++n;
			scanf("%lld",&z);
			if(z==3) st=n,z=1;
			if(z==4) en=n,z=1;
			d[i][j]=z;
		}
	}
	for(ll i=1;i<=a;i++){
		for(ll j=1;j<=b;j++){
			if(d[i][j]==2) continue;
			ll u=c[i][j];
			for(ll k=1;k<=8;k++){
				ll kx=i+x[k],ky=j+y[k];
				if(kx<1||kx>a||ky<1||ky>b) continue;
				if(d[kx][ky]==2) continue;
				ll v=c[kx][ky];
				e[u].push_back(make_pair(1-d[kx][ky],v));
			}
		}
	}
	memset(dis,0x3f3f3f,sizeof(dis));
	dis[st]=0;
	val[st]=1;
	q.push(make_pair(0,st));
	while(!q.empty()){
		ll u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(ll i=0;i<ll(e[u].size());i++){
			ll v=e[u][i].second,w=e[u][i].first;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				val[v]=val[u];
				q.push(make_pair(dis[v],v));
			}
			else if(dis[u]+w==dis[v]) val[v]+=val[u];
		}
	}
	if(dis[en]>1e18) printf("-1");
	else{
		printf("%lld\n%lld",dis[en],val[en]);
	}
}
2023/12/16 18:49
加载中...