题解 P6833 【[Cnoi2020]雷雨】

课间瞄了一眼，没看出来这是什么题/kk。上完课冷静一下发现确实像出题人所说的“经典模型”。 样例非常明显地告诉我们策略：一个二叉形状的闪电是最优的。 我们先分别考虑这两条路径 $O$ 到 $A$ 和 $O$ 到 $B$。$OA$ 和 $OB$ 显然不会交叉。如果有了交叉点 $C$，我们珂以找到一条更优的路径：从 $O$ 到 $C$ 再从 $C$ 到 $A,B$。 得到结论后，然后我们只需要枚举 $C$ 的位置即可。根据 $OC , AC , AB$ 的最短路算出二叉闪电的长度。 标程里用了带优先队列的 SPFA。然而我觉得这样做……很谔谔，于是就用了堆优 dijkstra。 ```cpp #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <queue> #include <vector> using namespace std; #define int long long struct node{ int x , y , v; bool operator < (const node &x) const { return x.v < v; } };const int N = 1000 + 5; int n , m , a , b , c; int disA[N][N] , disB[N][N] , disC[N][N]; int (*dis)[1005]; priority_queue<node> q; bool vis[N][N]; int map[N][N] , dd[4][2] = {{0 , 1} , {0 , -1} , {1 , 0} , {-1 , 0}}; bool p(int x , int y) { return 0 < x && x <= n && 0 < y && y <= m; } void ee(int d[][1005] , int x , int y) {//模板 dis = d; memset(vis , 0 , sizeof(vis)); q.push(node{x , y , map[x][y]}); while(!q.empty()) { node t = q.top(); q.pop(); int x = t.x , y = t.y , v = t.v; if(vis[x][y])continue; // printf("------------\%d %d\n" , x , y); vis[x][y] = true; dis[x][y] = v; for(int i = 0; i < 4; i++) { int dx = x + dd[i][0] , dy = y + dd[i][1]; if(!p(x , y) || vis[dx][dy])continue; q.push(node{dx , dy , v + map[dx][dy]}); } } } signed main() { scanf("%lld%lld%lld%lld%lld" , &n , &m , &a , &b , &c); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%lld" , &map[i][j]); ee(disA , 1 , a);ee(disB , n , b);ee(disC , n , c); // (1,a) 即为上文中的 O , (n , b) 是 A ， (n , c) 是 B (c++二维数组) // for(int i = 1; i <= n; i++ , puts("")) // for(int j = 1; j <= m; j++)printf("%lld " , disA[i][j]); int ans = 1e18; for(int i = 1; i <= n; i++) for(int j = 1; j <= m ;j++) ans = min(ans , disA[i][j] + disB[i][j] + disC[i][j] - 2 * map[i][j]); //因为 （i,j） 被计算了三遍。 printf("%lld\n" , ans); } ```