(Analysis by Mark Gordon)

This problem gives us a series of routes and associated costs and asks us to find the minimum cost to travel from city $A$ to city $B$ using them. In case there are multiple solutions with the same minimum cost we were also asked to compute the minimum number of cities that needed to be visited. Note that in some cases it may be necessary to make use of the same route more than one time (and for each use we would have to pay the cost of the route).

To solve this problem we can compute a matrix $\textit{cost}_{u,v}$ that gives the minimum cost (and for that min cost the min number of hops) to travel from $u$ to $v$. Then we can use Dijkstra's algorithm to find the cheapest path of intermediate cities that takes us from $A$ to $B$.

To compute $\textit{cost}_{u,v}$ we can for each route loop over each pair of cities $u, v$ such that $u$ appears before route $v$ and update $\textit{cost}_{u,v}$ with the cost of the route. This whole process takes $O(NM^2)$ where $M$ is the maximum length of each route.

Once this array is calculate we can apply Dijkstra's algorithm pretty directly. Note that while most competitors implemented a $O((V+E) \log V)$ heap-based algorithm it's actually more efficient (and arguably easier) in dense graphs to implement Dijkstra without a heap in $O(V^2)$ time. Below is my implementation of this solution

#include <iostream> #include <vector> #include <cstring> #include <cstdio> using namespace std; #define MAXV 1010 bool vis[MAXV]; pair<long long, int> cost_a2u[MAXV]; pair<long long, int> cost[MAXV][MAXV]; int main() { freopen("cowroute.in", "r", stdin); freopen("cowroute.out", "w", stdout); int A, B, N; cin >> A >> B >> N; /* Initialize cost matrix to infinity. */ memset(cost, 0x3F, sizeof(cost)); for (int i = 0; i < MAXV; i++) { cost[i][i] = make_pair(0, 0); } for (int i = 0; i < N; i++) { long long route_cost; int route_len; cin >> route_cost >> route_len; vector<int> route(route_len); for (int j = 0; j < route_len; j++) { cin >> route[j]; /* Update the cost from everything before this city to this city. */ for (int k = 0; k < j; k++) { cost[route[k]][route[j]] = min(cost[route[k]][route[j]], make_pair(route_cost, j - k)); } } } /* Perform Dijkstra without a heap in O(V^2) time. */ memset(vis, 0, sizeof(vis)); memset(cost_a2u, 0x3F, sizeof(cost_a2u)); cost_a2u[A] = make_pair(0, 0); for (int i = 0; i < MAXV; i++) { /* Find the closest unvisited vertex. */ int u = -1; for (int j = 0; j < MAXV; j++) { if (vis[j]) { continue; } else if (u == -1 || cost_a2u[j] < cost_a2u[u]) { u = j; } } /* Relax vertex u. */ vis[u] = true; for (int j = 0; j < MAXV; j++) { pair<long long, int> rlx = cost_a2u[u]; rlx.first += cost[u][j].first; rlx.second += cost[u][j].second; cost_a2u[j] = min(cost_a2u[j], rlx); } } /* Output the cheapest cost and length if possible. */ if (cost_a2u[B].second <= MAXV) { cout << cost_a2u[B].first << ' ' << cost_a2u[B].second << endl; } else { cout << "-1 -1\n"; } return 0; }