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;
}
