【Tsinsen】1228 飞飞侠【并查集优化最短路】

本文主要是介绍【Tsinsen】1228 飞飞侠【并查集优化最短路】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：A1228. 飞飞侠

#include <bits/stdc++.h>
using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 155 ;
const LL INF = 1e18 ;struct Node {LL dis ;int x , y ;Node () {}Node ( LL dis , int x , int y ) : dis ( dis ) , x ( x ) , y ( y ) {}bool operator < ( const Node& a ) const {return dis > a.dis ;}
} ;int a[MAXN][MAXN] ;
int b[MAXN][MAXN] ;
int p[MAXN][MAXN] ;
int sx[3] , sy[3] ;
LL d[MAXN][MAXN] ;
LL ans[3] ;
int n , m ;int F ( int p[] , int x ) {return p[x] == x ? x : ( p[x] = F ( p , p[x] ) ) ;
}void dij ( int o ) {for ( int i = 1 ; i <= n ; ++ i ) {for ( int j = 1 ; j <= m + 1 ; ++ j ) {d[i][j] = INF ;p[i][j] = j ;}}priority_queue < Node > q ;q.push ( Node ( b[sx[o]][sy[o]] , sx[o] , sy[o] ) ) ;p[sx[o]][sy[o]] = sy[o] + 1 ;d[sx[o]][sy[o]] = 0 ;while ( !q.empty () ) {Node u = q.top () ;q.pop () ;int l1 = a[u.x][u.y] , x = max ( 1 , u.x - l1 ) , y = min ( n , u.x + l1 ) ;for ( int i = x ; i <= y ; ++ i ) {int l2 = l1 - abs ( u.x - i ) , L = max ( 1 , u.y - l2 ) , R = min ( m , u.y + l2 ) ;for ( int j = F ( p[i] , L ) ; j <= R ; j = F ( p[i] , j ) ) {q.push ( Node ( u.dis + b[i][j] , i , j ) ) ;d[i][j] = u.dis ;p[i][j] = j + 1 ;}}}
}void solve () {for ( int i = 1 ; i <= n ; ++ i ) {for ( int j = 1 ; j <= m ; ++ j ) {scanf ( "%d" , &a[i][j] ) ;}}for ( int i = 1 ; i <= n ; ++ i ) {for ( int j = 1 ; j <= m ; ++ j ) {scanf ( "%d" , &b[i][j] ) ;}}for ( int i = 0 ; i < 3 ; ++ i ) {scanf ( "%d%d" , &sx[i] , &sy[i] ) ;}ans[0] = ans[1] = ans[2] = 0 ;for ( int i = 0 ; i < 3 ; ++ i ) {dij ( i ) ;for ( int j = 0 ; j < 3 ; ++ j ) {ans[j] += d[sx[j]][sy[j]] ;}}LL res = min ( ans[0] , min ( ans[1] , ans[2] ) ) ;if ( res >= INF ) printf ( "NO\n" ) ;else {printf ( "%c\n" , ans[0] == res ? 'X' : ( ans[1] == res ? 'Y' : 'Z' ) ) ;printf ( "%I64d\n" , res ) ;}
}int main () {while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;return 0 ;
}