社区讨论

为啥不能倒过来输入

P6833[Cnoi2020] 雷雨参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhjumrjj
此快照首次捕获于
2025/11/04 08:46
4 个月前
此快照最后确认于
2025/11/04 08:46
4 个月前
查看原帖
这样可以过
CPP
#include<bits/stdc++.h>
#define int long long
#define N 1010
using namespace std;
int s[N][N],n,m,a,b,c,minn=-1;
int d[3][N][N],vis[3][N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct node{
	int x;
	int y;
	int r;
	bool operator<(const node &t) const{
		return r>t.r;
	}
};
void dijkstra(int x,int y,int t){
	priority_queue<node>q;
	q.push({x,y,0});
	d[t][x][y]=s[x][y];
	while(!q.empty()){
		auto now=q.top();
		q.pop();
		int x=now.x;
		int y=now.y;
		if(vis[t][x][y]) continue;
		vis[t][x][y]=1;
		for(int i=0;i<4;i++){
			int sx=x+dx[i];
			int sy=y+dy[i];
			int sr=s[sx][sy];
			if(sx<1||sy<1||sx>n||sy>m) continue;
			if(d[t][sx][sy]==-1||d[t][sx][sy]>d[t][x][y]+sr){
				d[t][sx][sy]=d[t][x][y]+sr;
				q.push({sx,sy,d[t][sx][sy]});
			}
		}
	}
}
signed main(){
	cin>>n>>m>>a>>b>>c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>s[i][j];
		}
	}
	memset(d,-1,sizeof d);
	dijkstra(1,a,0);
	dijkstra(n,b,1);
	dijkstra(n,c,2);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			minn=min(minn,d[0][i][j]+d[1][i][j]+d[2][i][j]-s[i][j]*2);
			if(minn==-1) minn=d[0][i][j]+d[1][i][j]+d[2][i][j];
		}
	}
	cout<<minn;
	return 0;
}
但这样过不了
CPP
#include<bits/stdc++.h>
#define int long long
#define N 1010
using namespace std;
int s[N][N],n,m,a,b,c,minn=-1;
int d[3][N][N],vis[3][N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct node{
	int x;
	int y;
	int r;
	bool operator<(const node &t) const{
		return r>t.r;
	}
};
void dijkstra(int x,int y,int t){
	priority_queue<node>q;
	q.push({x,y,0});
	d[t][x][y]=s[x][y];
	while(!q.empty()){
		auto now=q.top();
		q.pop();
		int x=now.x;
		int y=now.y;
		if(vis[t][x][y]) continue;
		vis[t][x][y]=1;
		for(int i=0;i<4;i++){
			int sx=x+dx[i];
			int sy=y+dy[i];
			int sr=s[sx][sy];
			if(sx<1||sy<1||sx>n||sy>m) continue;
			if(d[t][sx][sy]==-1||d[t][sx][sy]>d[t][x][y]+sr){
				d[t][sx][sy]=d[t][x][y]+sr;
				q.push({sx,sy,d[t][sx][sy]});
			}
		}
	}
}
signed main(){
	cin>>n>>m>>a>>b>>c;
	for(int i=n;i>=1;i--){
		for(int j=1;j<=m;j++){
			cin>>s[i][j];
		}
	}
	memset(d,-1,sizeof d);
	dijkstra(n,a,0);
	dijkstra(1,b,1);
	dijkstra(1,c,2);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			minn=min(minn,d[0][i][j]+d[1][i][j]+d[2][i][j]-s[i][j]*2);
			if(minn==-1) minn=d[0][i][j]+d[1][i][j]+d[2][i][j];
		}
	}
	cout<<minn;
	return 0;
}
蒟蒻求调

回复

0 条回复,欢迎继续交流。

正在加载回复...