TopCoder SRM 622 DIV 1 BuildingRoutes

As expected still the only ability to solve first one. Quiet a straightforward problem directive use shortest path to solve.  Let f[i][j] be the shortest distance between vertex i and j. If f[i][j] == f[i][x] + dist[x][y] + f[y][j], then the edge ( x,y ) will be used in the path from i to j.  Here reviews two method to calculate the shortest path from each vertex to each vertex in the graph.

The better way here is to use Floyd algorithm which runs in O(|V|^3).

 
    void Floyd(vector<vector<int> >&f){ 
        int n=f.size(); 
        for(int k=0;k<n;k++) 
        for(int i=0;i<n;i++) 
        for(int j=0;j<n;j++) 
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]); 
    } 

The Dijkstra get the distance from one vertex to each vertex once time which runs in O(|E| + |V|log*|V|) using fibonacci heap. Using STL priority_queue there is no update method, the substitute method is inserting the new node each time instead of update the priority. (Here my first time using STL priority queue and suffering a long time to fix a tiny bug in function object passed as priority_queue template :(

    struct Node{ 
        int p,v; 
        Node(int a,int b):p(a),v(b){} 
    }; 
    struct cmp{ 
        bool operator()(const Node& n1, const Node& n2){ 
            return n1.v>n2.v; 
        } 
    }; 
    void Dijkstra(vector<vector<int> >&f){ 
        int n=f.size(); 
        for(int s=0;s<n;s++){ 
            vector<bool> vis(n,false); 
            priority_queue<Node,vector<Node>,cmp> pq; 
            for(int i=0;i<n;i++) 
                pq.push(Node(i,f[s][i])); 
            while(!pq.empty()){ 
                int v=pq.top().p; 
                pq.pop(); 
                if(vis[v])continue; 
                vis[v]=true; 
                for(int i=0;i<n;i++) 
                    if(f[s][i]>f[s][v]+f[v][i]){ 
                        f[s][i]=f[s][v]+f[v][i]; 
                        pq.push(Node(i,f[s][i])); 
                    } 
            } 
        } 
    } 

The source code can be found at StackOverflow. (But a critical fault he made there)

Note.(1) The template parameters of STL priority_queue. The compare function said that 

The expression comp(a,b), where comp is an object of this type and a and b are elements in the container, shall return true if a is considered to go before b in the strict weak ordering the function defines.

Thus in the Dijkstra algorithm the node with smaller value has higher priority. The Compare function should be  n1.v>n2.v 

Note.(2) Say in the Dijkstra algorithm, we init the distance array int d[]={INT_MAX}. After that we use the condition if d[x]+y the attention should be paid that overflow might happen.