Luogu P6833 【[Cnoi2020]雷雨】
这道题赛时的时候想了一个奇怪的做法但是没过，后来经过Stay_hungry的提示就码了这道题。
雷电必定会在一点处分叉，分别电击地上的两个点，我们只需要枚举这个分叉点。那么怎么算出这个点和目标点的距离呢，很容易可以想到用最短路来求解。在仔细算一下复杂度\(O({V}log{E}+n^2)\) (\(V\)为点的个数 \(E\)为边的个数)
这道题其实可以转化为图论题，就是从起点和两个终点分别跑一遍最短路，然后枚举那个闪电⚡分开的点，在将三个\(dis_x\)(\(x\)为当前枚举的点的编号)加起来，取个\(Min\)就可以了。
细节处理都在代码中
//必须要开 long long 不然电阻R加起来会炸
//但是#define int long long 会MLE
//所以就把几个dis数组开long long就好了
#include <bits/stdc++.h>
#define Reg register
using namespace std;
const int N=1e3+10;
inline long long Min(long long a,long long b) { return a<b?a:b; }
inline int read() {
int x=0,f=0; char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?-x:x;
}
struct node {
int u;
long long d;
inline bool operator <(const node &rhs) const {
return d>rhs.d;
}
} ;
struct Edge {
int next,to,w;
} edge[N*N*6];
int n=read(),m=read(),sx=read(),e1=read(),e2=read(),tot;
long long ans=5e18;
int head[N*N],a[N][N];
long long diss[N*N],dis1[N*N],dis2[N*N];
//建边
inline void Addedge(int u,int v,int w) {
edge[++tot]=(Edge){head[u],v,w};
head[u]=tot;
}
//Dijkstra
inline void Dijkstra(int s,long long *dis) {
for(Reg int i=1;i<=n*m;i++)
dis[i]=5e18;
//将起点的初值设置为这个位置的电阻值
if(s%m)
dis[s]=a[s/m+1][s%m];
else
dis[s]=a[s/m][m];
priority_queue<node>que;
que.push((node){s,0});
while(!que.empty()) {
node front=que.top(); que.pop();
int u=front.u;
// if(d==dis[u])
for(Reg int i=head[u];i;i=edge[i].next) {
int v=edge[i].to,w=edge[i].w;
// cout<<u<<' '<<v<<' '<<w<<'\n';
if(dis[u]+w<dis[v]) {
dis[v]=dis[u]+w;
que.push((node){v,dis[v]});
}
}
}
}
signed main() {
//将网格图转化为有向图
for(Reg int i=1;i<=n;i++)
for(Reg int j=1;j<=m;j++) {
a[i][j]=read();
//将每个点的编号设为从左往右数，从上往下数第几个
//连边时连的是它四周的四个点连向它自己，所以边权是为这个点的电阻值
if(j>1)//这是防止向上一个网格连的时候越界，下同
Addedge((i-1)*m+j-1,(i-1)*m+j,a[i][j]);
if(j<m)
Addedge((i-1)*m+j+1,(i-1)*m+j,a[i][j]);
if(i>1)
Addedge((i-2)*m+j,(i-1)*m+j,a[i][j]);
if(i<n)
Addedge(i*m+j,(i-1)*m+j,a[i][j]);
}
Dijkstra(sx,diss)/*,puts("---")*/,Dijkstra(m*(n-1)+e1,dis1)/*,puts("---")*/,Dijkstra(m*(n-1)+e2,dis2);
//跑三遍Dijkstra
//枚举中间点
for(Reg int i=1;i<=n;i++)
for(Reg int j=1;j<=m;j++)
//因为中间点会被计算三次，所以要减去两次
ans=Min(ans,diss[(i-1)*m+j]+dis1[(i-1)*m+j]+dis2[(i-1)*m+j]-2*a[i][j])/*,printf("I=%d,J=%d,Dis=%d,%d,%d\n",i,j,diss[(i-1)*m+j],dis1[(i-1)*m+j],dis2[(i-1)*m+j])*/;
cout<<ans<<'\n';
return 0;
}
