## Editorial for CCC '21 S4 - Daily Commute

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

#### Subtask 1

Every possible path is a prefix of the permutation of integers , so trying all permutations each day suffices.

**Time Complexity:**

#### Subtask 2

If a DFS algorithm is used to compute the shortest distance from to on each day, we can prove that the algorithm has a complexity of per day.

The DFS implementation being discussed is something similar to the following (though more code is needed to account for the subway).

```
vector<int> g[200005];
int dist[200005];
void dfs(int u) {
int d = dist[u] + 1;
for (int v: g[u]) {
if (dist[v] > d) {
dist[v] = d;
dfs(v);
}
}
}
// DFS call. Run once per day
memset(dist, 0x3f, sizeof dist); // set all distances to "infinity" value
dist[n] = 0;
dfs(n);
```

Code credit:

We can prove this by considering the amount of times DFS is called for each node in the graph. From the implementation, it's evident that `dfs`

is called every time the shortest distance to a node "improves", and as the shortest distance to a node in the graph is bounded by , its distance can improve at most times. This means that `dfs`

will be called at most times for each node and each edge will be checked at most times.

**Time Complexity:**

#### Subtask 3

For each day, run a weighted SSSP algorithm such as Dijkstra's. Note that the subway has to be treated differently from the walkways as waiting for the subway needs to be accounted for.

**Time Complexity:**

#### Subtask 4

We can prove that an optimal answer always exists with the following constraints:

- Take some prefix of the subway
- Exit the subway and walk to node using exclusively walkways

Assume that the only optimal trips do not respect the above constraints. Let be the node where we leave the subway for the final time on the trip. If we simply take the subway from to instead and then take walkways from to , it will be at least as good as the optimal trip, because the subway always arrives at at the same time no matter what path we take.

Thus, on each day, we simply have to check these candidate solutions for an optimal answer. And as only two stations will change positions each day, we just need a data structure that supports efficient point updates and minimum queries to maintain the solution. Examples include `std::multiset`

in C++, `TreeSet`

in Java, and the `heapq`

package in Python (a bit more effort is needed for a priority queue to work though).

**Time Complexity:**

## Comments

recursive dfs faced TLE :(

I tried BFS here, but I'm getting TLE on batch 4. I think I have to also store the steps it took to reach a station to speed up my solution?

Look at your time complexity. Looks something like .

Is my approach in the right direction though? Or do I have to use another algorithm?

Try to find a method that doesn't perform a complete search of the graph each query, such as the editorial above.

I tried something similar to that, but I started from and went to . I passed #4 but I got TLE on #5: https://dmoj.ca/submission/3633167

Do I have to start at and go to ?

Changes in trains can be treated as qurries. Instead of computing them again and again(in ur case the BFS) for each qurry(change), you should avoid doing repetitive work.

I'm not sure how to treat the trains as queries though in my current solution?

see the editorial above.

Would BFS work as well?

Yes, BFS works too