vector<vector<int>> direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool isInVaildBoardary(vector<vector<int>> &grid, int row, int col) {
    int m = grid.size(), n = grid[0].size();
    if (row >= 0 && row < m && col >= 0 && col < n) {
        return true;
    }
    return false;
}

struct comp {
    bool operator()(pair<int, int> &a, pair<int, int> &b) {
        return a.second > b.second;
    }
};
// 邻接矩阵做的迪杰斯特拉算法
int Dijkstra(vector<vector<int>> &graph, int source, int target,
             int N) { // 1.......N
    // auto graph = vector<vector<int>>(N + 1, vector<int>(N + 1, -1));
    vector<bool> visited(N + 1, false);
    visited[0] = true;
    priority_queue<pair<int, int>, vector<pair<int, int>>, comp> minStack;
    minStack.push({source, 0});//第二个参数是距离
    while (!minStack.empty()) {
        auto current = minStack.top();
        minStack.pop();
        int arrived = current.first;
        if (visited[arrived]) {
            continue;
        }
        if (arrived == target) {
            return current.second;
        }
        visited[arrived] = true;
        for (int i = 0; i <= N; i++) {
            if (!visited[i] && graph[arrived][i] >= 0) {
                minStack.push(make_pair(i, current.second + graph[arrived][i]));
            }
        }
    }
    return -1;
}

// 边来做的迪杰斯特拉算法
int Dijkstra2(unordered_map<int, vector<pair<int, int>>> &graph, int source,
              int target, int N) {
    vector<bool> visited(N + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, comp> minStack;
    minStack.push({source, 0});
    while (!minStack.empty()) {
        auto current = minStack.top();
        minStack.pop();
        int arrived = current.first;
        if (visited[arrived]) {
            continue;
        }
        if (arrived == target) {
            return current.second;
        }
        visited[arrived] = true;
        for (int i = 0; i < graph[arrived].size(); i++) {
            if (!visited[graph[arrived][i].first]) {
                minStack.push(
                    make_pair(graph[arrived][i].first,
                              current.second + graph[arrived][i].second));
            }
        }
    }
    return -1;
}

int Bellman_Ford(vector<vector<int>> &times, int N, int source, int target) {
    vector<int> dist(N + 1, INT_MAX);
    dist[source] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < times.size(); j++) {
            int u = times[j][0], v = times[j][1], w = times[j][2];
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    return dist[target] == INT_MAX ? -1 : dist[target];
}

// union find解法
/*
class UnionFind{
        int[] father;
        int[] count;
        UnionFind(int len) {
            father = new int[len];
            count = new int[len];
            for (int i = 0; i < len ; i++) {
                father[i] = i;
                count[i] = 1;
            }
        }
        int find(int toFind) {
            while(father[toFind] != toFind) {
                father[toFind] = father[father[toFind]];
                toFind = father[toFind];
            }
            return toFind;
        }
        void union(int a, int b) {
            int fatherA = find(a);
            int fatherB = find(b);
            if (fatherA != fatherB) {
                father[fatherA] = fatherB;
                count[fatherB] += count[fatherA];
            }
        }
    }
*/