社区讨论
为啥不能倒过来输入
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 条回复,欢迎继续交流。
正在加载回复...