P4268 [USACO18FEB] Directory Traversal G

Bessie the cow is surprisingly computer savvy. On her computer in the barn, she stores all of her precious files in a collection of directories; for example: ``` bessie/ folder1/ file1 folder2/ file2 folder3/ file3 file4 ``` There is a single "top level" directory, called bessie. Bessie can navigate to be inside any directory she wants. From a given directory, any file can be referenced by a "relative path". In a relative path, the symbol ".." refers to the parent directory. If Bessie were in folder2, she could refer to the four files as follows: ``` ../file1 file2 ../../folder3/file3 ../../file4 ``` Bessie would like to choose a directory from which the sum of the lengths of the relative paths to all the files is minimized.

N/A

N/A

This input describes the example directory structure given above. The best solution is to be in folder1. From this directory, the relative paths are: ``` file1 folder2/file2 ../folder3/file3 ../file4 ``` Problem credits: Mark Gordon