1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 0x3fffffff;
int direct[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<vector<bool> > water;
vector<int> A,B;
int N, M, K, Q;
int spfa(int sx, int sy, int ex, int ey){
    vector<vector<int> > dist(M, vector<int>(N, INF));
    vector<vector<int> > inque(M, vector<int>(N, 0));
    dist[sx][sy] = 0;
    queue<pair<int, int> > que;
    que.push(make_pair(sx, sy));
    dist[sx][sy] = 0;
    inque[sx][sy] = 1;
    pair<int, int> front, next;
    while(!que.empty()){
        front = que.front();
        que.pop();
        inque[front.first][front.second] = 0;
        for(int i = 0; i < 4; i++){
            next.first = front.first + direct[i][0];
            next.second = front.second + direct[i][1];
            if(next.first >= 0 && next.first < M && next.second >= 0 && next.second < N && !water[next.first][next.second]){
                int len = 0;
                if(next.first != front.first)
                    len = next.first > front.first ? A[front.first] : A[next.first];
                else len = next.second > front.second ? B[front.second] : B[next.second];
                if(dist[front.first][front.second] + len < dist[next.first][next.second]){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX