codeforces 821 D. Okabe and City（最短路）

题目链接：http://codeforces.com/contest/821/problem/D

题意:n*m地图,有k个位置是点亮的,有4个移动方向,每次可以移动到相邻的点亮位置,每次站在初始被点亮某个位置,暂时使某行或该某列全部点亮,花费为1,下一次使用时,上一次暂时点亮被熄灭

题解：显然只要知道如果两点相邻直接相连然后就是极限情况，什么情况之下是两点是连不到一起的。如果x轴与y轴的相差大于2是连不到一起的。

具体画一下图就知道了。然后就跑一遍dij+优先队列就行了或者spfa也行。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#define inf 0X3f3f3f3f
using namespace std;
const int M = 1e4 + 10;
typedef long long ll;
ll dis[M];
bool vis[M];
int n , m , k , flag;
struct TnT {
    int x , y;
}T[M];
struct qnode {
    int v;
    ll c;
    qnode(int v , ll c):v(v) , c(c) {}
    bool operator <(const qnode &r) const{
        return c > r.c;
    }
};
void dij() {
    priority_queue<qnode>q;
    memset(vis , false , sizeof(vis));
    q.push(qnode(1 , 0));
    dis[1] = 0;
    while(!q.empty()) {
        int u = q.top().v;
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = 1 ; i <= k ; i++) {
            int v = i;
            int dx = abs(T[u].x - T[v].x) , dy = abs(T[u].y - T[v].y);
            if(dx + dy == 1) {
                if(!flag && T[v].x == n && T[v].y == m) {
                    if(dis[v] > dis[u] + 1 && !vis[v]) {
                        dis[v] = dis[u] + 1;
                        q.push(qnode(v , dis[v]));
                    }
                }
                else {
                    if(dis[v] > dis[u] && !vis[v]) {
                        dis[v] = dis[u];
                        q.push(qnode(v , dis[v]));
                    }
                }
            }
            else {
                if(dx <= 2 || dy <= 2) {
                    if(!flag) {
                        if(T[v].x == n && T[v].y == m) {
                            if(dx <= 1 || dy <= 1) {
                                if(dis[v] > dis[u] + 1 && !vis[v]) {
                                    dis[v] = dis[u] + 1;
                                    q.push(qnode(v , dis[v]));
                                }
                            }
                        }
                        else {
                            if(dis[v] > dis[u] + 1 && !vis[v]) {
                                dis[v] = dis[u] + 1;
                                q.push(qnode(v , dis[v]));
                            }
                        }
                    }
                    else {
                        if(dis[v] > dis[u] + 1 && !vis[v]) {
                            dis[v] = dis[u] + 1;
                            q.push(qnode(v , dis[v]));
                        }
                    }
                }
            }
        }
    }
}
int main() {
    flag = 0;
    scanf("%d%d%d" , &n , &m , &k);
    for(int i = 1 ; i <= k ; i++) {
        scanf("%d%d" , &T[i].x , &T[i].y);
        if(T[i].x == n && T[i].y == m) flag = 1;
        dis[i] = inf;
    }
    if(!flag) {
        T[k + 1].x = n , T[k + 1].y = m;
        k++;
        dis[k] = inf;
    }
    dij();
    if(dis[k] >= inf) printf("%d
" , -1);
    else printf("%lld
" , dis[k]);
    return 0;
}