XDOJ 1202: The Offer - Lunatic

题目链接：

题目大意：给定一个$n \times m$的网格图，每个格子上有值$h[i][j]$。有两种移动方式：1.移动到相邻的格子（代价为原位置和移动后位置上的值之和）；2.在给定的$k$个矩形内，若两个格子值相差不超过$p[k]$，则可互相移动（代价为$t[k]$）。现给定起点坐标和终点坐标，问最小代价。

Dijkstra

关键在于建图，建好图后直接跑最短路就好了。

给每个矩形设$3 \times 101$个虚点，将该矩形内$h[i][j]=x$的点分别与三个虚点$d_x^1,d_x^2,d_x^3$相连（其中$d_x^1$指向点$(i,j)$（边长为$0$），点$(i,j)$指向$d_x^2$（边长为$0$），$d_x^3$与点$(i,j)$互相连接（边长为$t[k]$）），最后将符合条件（$fabs(a-b)  \leqslant p[k]$）的$d_a^1$点与$d_b^2$点相连接（边长为$2 \times t[k]$）。

（考虑到$t[k]$可能不能被$2$整除，将所有边长乘$2$，再将结果除$2$）。

具体结构如下图所示（请叫我灵魂画师，不接受批评歇歇）：

最后将相邻格子互相连边，跑下Dijkstra即可。

建图复杂度为$O(rn^2MAX\{h[i][j]\})$，故总复杂度为$O(rn^2MAX\{h[i][j]\}+n^2logn)$.

代码如下：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #define N 105  6 #define R 15  7 #define X first  8 #define Y second  9 using namespace std; 10 typedef long long ll; 11 typedef pair
         
           P; 12 const ll inf=1000000000000000LL; 13 ll CASE,mp[N][N],n,m,r,t[R],p[R],dis[N*N+3*R*N]; 14 bool vis[N*N+3*R*N]; 15 P a[R],b[R],S,T; 16 struct edge{ 17     ll to,w; 18     edge(ll T,ll W){to=T;w=W;} 19 }; 20 struct node{ 21     ll u,d; 22     node(ll U,ll D){u=U;d=D;} 23     bool operator < (const node x)const{
   return d>x.d;} 24 }; 25 vector
          
           e[N*N+3*R*N]; 26 priority_queue
           
            q; 27 void init(){ 28 for(ll i=0;i