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.

How to debug the STL containers

Because the STL Containers are not basic data types such as int or array thus sometimes hard to directly display the value of a container such as vector in debug.

Here is a simple way rather then  using static debug. We can add the display statement in source code rather then invoking them in the program, we can call the at gdb when debug. Write an auxiliary that can display the property of variable what you want, and call that function in runtime of gdb. Note that the output stream should be cerr.

This is the source code in which you can see the function gdb_display is used to show the vector data when debug. Here is how to call it in gdb

According to the different vector passed into gdb_display, different vector shows.

A brief summary over STL Container

Here is a brief summary talking about common STL Container used in Leetcode problems.

1. Sequence Containers:
1. Vector. 
1. Just like the array in c language that random access runs in constant time. 
2. Implemented by the dynamic array ensuring that the amortized time of push_back and pop_back is constant time. 
3. Modify elements other then the last element run in O(n) time 
2. Deque.
1. Random access runs in constant time as well
2. Implemented by double dynamic array I guess thus can push and pop elements both at the end and the front in constant time
3. Modify elements other than the first and last elements run in O(n) time.
3. List
1. Like linked list in c language that random access will runs in O(n) time
2. Obviously that insert and delete element run in constant time
2. Container Adapters:
1. Stack and Queue.
2. Priority Queue
3. Associative Containers:
1. Set.
1. Implemented by binary search tree (not hash table), thus the time complexity of insert and erase are O(logn)
2. Map
1. The same method with set thus [ ]  operator is O(logn)
3. Unordered_Set and Unordered_Map
1. New in C++11 that insert erase and [] operators run in O(1) or O(n)
2. Implemented by hash table
3. The advantage of set over unordered_set is set requires limited memory in proportion to the input size

Sequnce Containers can be used in Sort function directly with customized compare function.