求有向图的最短路径

Description:

Find the minimum cost to reach destination using a train
There are N stations on route of a train. The train goes from station 0 to N-1. The ticket cost for
all pair of stations (i, j) is given where j is greater than i. Find the minimum cost to reach the
destination.

Example:

Input:
cost[N][N] = { {0, 15, 80, 90},
{INF, 0, 40, 50},
{INF, INF, 0, 70},
{INF, INF, INF, 0}
};
There are 4 stations and cost[i][j] indicates cost to reach j
from i. The entries where j < i are meaningless.
Output:
The minimum cost is 65

完整代码：

//Q5
//we can use Dijkstra algorithm to solve this problem
//the time complexity will be O(N^2) where N is the number of stations
//if we can use Fibonacci heap for this case, the running time will be down to O(E + NlogN)
//but STL doesn't include any implementation for Fibonacci heap (boost may have)
//so we wouldn't use normal heap sort, otherwise, the running time will up to O(N^2 * logN)
int minimumCost(int n, vector<vector<int>>& cost) {
    vector<int> weights;
    unordered_set<int> unCheck;
    for(int i = 0; i < n; i++) {
        if(i == 0)
            weights.push_back(0);
        else 
            weights.push_back(INT_MAX);
        unCheck.insert(i);
    }
    while(!unCheck.empty()) {
        //we use a scan to find out the heap top instead of use heap sort
        int minWeight = INT_MAX;
        int next;
        for(int i: unCheck) {
            if(weights[i] < minWeight) {
                minWeight = weights[i];
                next = i;
            }
        }
        //remove node from set
        unCheck.erase(next);
        //update weights
        for(int i = next; i < n; i++) {
            weights[i] = min(weights[i], weights[next] + cost[next][i]);
        }
    }
    return weights[n - 1];
}