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 and a full weighted directed graph of at most vertices, where is the weight of the edge connecting vertex with vertex . The task is to count a sum of weights of overloaded edges. An edge is overloaded if and only if there are at least pairs of vertices such that lies on any shortest path between and . 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 denote the distance between and . 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 lies on any shortest path between given vertices and . Of course we cannot generate all shortest paths from to , because the number of such paths can be . The most clever method to check it is to observe that:

lies on any shortest path from to if and only if

This can be checked in 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 .

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; } };