https://leetcode.com/contest/leetcode-weekly-contest-49/problems/cut-off-trees-for-golf-event/

http://alrightchiu.github.io/SecondRound/all-pairs-shortest-pathfloyd-warshall-algorithm.html


http://slideplayer.com/slide/4393766/14/images/28/Some+Algorithms+When+no+negative+edges.jpg

https://stackoverflow.com/questions/26547816/understanding-time-complexity-calculation-for-dijkstra-algorithm

void Solution::dijkstraSingleSource(vector<list<pair<int, int> > > &edge, int src)
{
    set< pair<int, int> > active_vertices;
    active_vertices.insert(make_pair(0, src));

    while (active_vertices.size() != 0) {
        int vertex = (active_vertices.begin())->second;
        active_vertices.erase(make_pair(shortestDist[src][vertex], vertex));

        list<pair<int, int> >::iterator iter;
        for (iter = edge[vertex].begin(); iter != edge[vertex].end(); iter++) {
            int dist       = iter->first;
            int edgeLength = iter->second;
            if ((shortestDist[src][vertex] + edgeLength) < shortestDist[src][dist]) {
                active_vertices.erase(make_pair(shortestDist[src][dist], dist));
                shortestDist[src][dist] = (shortestDist[src][vertex] + edgeLength);
                active_vertices.insert(make_pair(shortestDist[src][dist], dist));
            }
        } 
    }
}

void Floyd_Warshall(vector<vector<pair<int, int> > > &edges, vector<vector<int> > &shortest)
{
    int none = -1;
    int n = edges.size();
    if (n == 0) {
        return;
    }
    if (shortest.size() != n) {
        return;
    }
    for (int i = 0; i < n; i++) {
        if ((shortest[i].size()) != n)
            return;
    }

    // initialize shortest
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                shortest[i][j] = 0;
            } else {
                shortest[i][j] = INT_MAX;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < edges[i].size(); j++) {
            shortest[i][edges[i][j].first] = edges[i][j].second;
        }
    }

    for (int maxHalfway = 0; maxHalfway < n; maxHalfway++) {
        for (int source = 0; source < n; source++) {
            for (int dist = 0; dist < n; dist++) {
                if (shortest[source][maxHalfway] != INT_MAX && shortest[maxHalfway][dist] != INT_MAX) {
                    if (shortest[source][dist] > (shortest[source][maxHalfway] + shortest[maxHalfway][dist])) {
                        shortest[source][dist] = (shortest[source][maxHalfway] + shortest[maxHalfway][dist]);
                    }
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (shortest[i][j] != INT_MAX)
                printf("%2d  ", shortest[i][j]);
            else
                printf("%2d  ", none);
        }
        printf("\n");
    }

}