Tag Archives: ShortestPath

TopCoder / SRM 622 div1 250

SRM 622 took place 10 hours ago, but I didn't participate because it was in the middle of the night in Poland. Here's a quick post on the 250 problem.

250 Problem

You're given an integer T and a full weighted directed graph of at most N \leq 50 vertices, where w_{i,j} is the weight of the edge connecting vertex i with vertex j. The task is to count a sum of weights of overloaded edges. An edge e is overloaded if and only if there are at least T pairs of vertices (v, u) such that e lies on any shortest path between v and u. The full problem statement is here SRM 622 div1 250.

The simplest method that came to my mind is to first compute the lengths of shortest paths between all pairs of vertices. Let d_{v, u} denote the distance between v and u. During the contest, the crucial thing here is to use the Floyd-Warshall algorithm rather than for example Dijkstra, not because it's faster, but because it's significantly easier to code.

It remains to decide if an edge e = (v, u) lies on any shortest path between given vertices s and t. Of course we cannot generate all shortest paths from s to t, because the number of such paths can be \Omega(2^n). The most clever method to check it is to observe that:

e = (v, u) lies on any shortest path from s to t if and only if

d_{s, t} = d_{s, v} + w_{v, u} + d_{u, t}

This can be checked in O(1) time because we've just computed distances for all pairs of vertices.

The time complexity of my algorithm is dominated by the cost of doing the above check for the whole graph. For each pair of verices, we iterate over all edges and do a constant time work which results in O(n^4).

Here's my code:

const int MAX_N = 55;

int d[MAX_N][MAX_N];
int cnt[MAX_N][MAX_N];
class BuildingRoutes {
    public:
    int build(vector w, int T) {
        int n = w.size();
        FOR(i, n) FOR(j, n) d[i][j] = w[i][j] - '0';
        FOR(k, n)
        {
            FOR(i, n)
            {                
                FOR(j, n)
                {
                    REMIN(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        FOR(s, n)
        {
            FOR(t, n)
            {
                FOR(i, n)
                {
                    FOR(j, n)
                    {
                        if(d[s][t] == d[s][i] + (w[i][j] - '0') + d[j][t]) 
                            cnt[i][j]++;
                    }
                }
            }
        }
        int res = 0;
        FOR(i, n)
        {
            FOR(j, n)
            {
                if(cnt[i][j] >= T) res += w[i][j] - '0';
            }
        }
        return res;
    }
};