当前位置：首页 > news >正文

打卡信奥刷题（3061）用C++实现信奥题 P6833 [Cnoi2020] 雷雨

news 2026/5/24 3:27:26

P6833 [Cnoi2020] 雷雨

题目背景

令人不安的云开始笼罩天空。
巨大的建筑在强风中轧轧作响。
幻想乡中响彻着不和协音。
——「东方辉针城～ Double Dealing Character」

一个雷雨交加的夜晚，一束闪电击中了雾之湖畔的红魔馆和迷途竹林。

似乎有什么大事要发生，Cirno 在小屋静静地中思考着。

题目描述

幻想乡的纵切面可以抽象成一个n×mn\times mn×m的矩形。

其中每一个1×11\times 11×1的单元格(i,j)(i,j)(i,j)都有一个电阻计量值(虚构的概念)Ri,jR_{i,j}Ri,j。

闪电从雷雨云上的O(n,a)\texttt{O}(n,a)O(n,a)发出，击中了地面上的红魔馆A(1,b)\texttt{A}(1,b)A(1,b)与迷途竹林B(1,c)\texttt{B}(1,c)B(1,c)。

雷电是自然的造物，所以覆盖的位置电阻计量值总和最小，即从O\texttt{O}O到A\texttt{A}A与B\texttt{B}B的两条路径的并集的电阻计量值的和最小。

所以在所有位置电阻计量已知的情况下，Cirno 想知道雷电的经过的路径的最小电阻计量值的和。

输入格式

第一行，五个整数n,m,a,b,cn,m,a,b,cn,m,a,b,c。(0<a,b,c≤m)(0<a,b,c\le m)(0<a,b,c≤m)

以下nnn行，每行mmm个整数，表示电阻计量Ri,jR_{i,j}Ri,j，其中第一行表示雷雨云，最后一行表示地面。

输出格式

一行，一个整数，表示答案。

输入输出样例 #1

输入 #1

5 5 1 2 4 1 8 1 6 6 1 1 1 2 4 8 3 1 2 2 1 2 1 9 1 1 0 9 1 1

输出 #1

说明/提示

样例解释

如图黄色线为闪电的路径。

数据范围与约定

对于100%100\%100%的数据保证：0<n,m≤10000<n,m \le 10000<n,m≤1000，0≤Ri,j≤1090 \le R_{i,j}\le 10^90≤Ri,j≤109，0<a,b,c≤m0< a,b,c \le m0<a,b,c≤m。

子任务「本题采用捆绑测试」

Subtask1（10%10\%10%）:Ri,j∈{1}R_{i,j}\in\{1\}Ri,j∈{1}。
Subtask2（10%10\%10%）:Ri,j∈{0,1}R_{i,j}\in\{0,1\}Ri,j∈{0,1}。
Subtask3（10%10\%10%）:a=b=ca=b=ca=b=c。
Subtask4（10%10\%10%）:n,m≤5n,m \le 5n,m≤5。
Subtask5（60%60\%60%）: 无特殊限制。

C++实现

#include<bits/stdc++.h>#defineN1009#defineINF0x3f3f3f3f3f3f3f3fusingnamespacestd;typedeflonglongll;inlinellread(){ll x=0,f=1;intc=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}returnx*f;}ll n,m,a,b,c,r[N][N],dst[3][N][N],ans=INF,vst[N][N];constll dx[4]={1,0,0,-1},dy[4]={0,1,-1,0};//扩展方向structNODE{ll x,y,v;booloperator<(constNODE&a)const{returnv>a.v;//小根堆的bool operator}};voidbfs(ll t,ll tx,ll ty){fill(vst[0],vst[0]+N*N,0);priority_queue<NODE>q;q.push((NODE){tx,ty,dst[t][tx][ty]});while(!q.empty()){NODE x=q.top();q.pop();if(vst[x.x][x.y])continue;vst[x.x][x.y]=1;for(inti=0;i<4;i++){ll nx=x.x+dx[i],ny=x.y+dy[i];if(nx<1||nx>n||ny<1||ny>m||vst[nx][ny])continue;dst[t][nx][ny]=min(dst[t][nx][ny],dst[t][x.x][x.y]+r[nx][ny]);q.push((NODE){nx,ny,dst[t][nx][ny]});}}}intmain(){n=read(),m=read(),a=read(),b=read(),c=read();for(inti=n;i>=1;i--)for(intj=1;j<=m;j++)r[i][j]=read();fill(dst[0][0],dst[0][0]+3*N*N,INF);dst[0][n][a]=r[n][a];//初始化dst[1][1][b]=r[1][b];dst[2][1][c]=r[1][c];bfs(0,n,a);bfs(1,1,b);bfs(2,1,c);//三遍bfs求完d数组for(inti=1;i<=n;i++)for(intj=1;j<=m;j++){ans=min(ans,dst[0][i][j]+dst[1][i][j]+dst[2][i][j]-2*r[i][j]);}printf("%lld",ans);return0;}