Algorithm Designda67_f_travelling_tourist
Travelling Tourist
1a99d18c-c730-4f56-a839-ac7d1ba1fcd2.cppC++
1// Loading code...Selected Submission
100 / 100
0.052s
4628 KB
Shortest PathBacktrack
Time Comp.
O(D^2 * E log V + D!) where D is the number of destinations, E is the number of edges, and V is the number of vertices. Dijkstra's is O(E log V) and is called D^2 times. The permutation part is O(D!).
Space Comp.
O(V^2 + D)
Readability
5/10
"The code calculates the shortest path between all pairs of destination nodes using Dijkstra's algorithm and then finds the minimum cost to visit all destinations in any order using permutations. Thus, it combines shortest path finding with a brute-force search through all possible orderings."
History
| Attempt | Points | Time ↓ |
|---|---|---|
| Try #33 | 100 | 5/1/2025 |
| Try #32 | 100 | 5/1/2025 |
| Try #31 | 100 | 5/1/2025 |
| Try #30 | 100 | 4/22/2025 |
| Try #29 | 100 | 4/22/2025 |
| Try #28 | 100 | 4/22/2025 |
| Try #27 | 0 | 4/22/2025 |
| Try #26 | 0 | 4/22/2025 |
| Try #25 | 100 | 4/22/2025 |
| Try #24 | 100 | 4/22/2025 |
| Try #23 | 5 | 4/22/2025 |
| Try #22 | 0 | 4/14/2025 |
| Try #21 | 0 | 4/14/2025 |
| Try #20 | 0 | 4/14/2025 |
| Try #19 | 100 | 4/14/2025 |
| Try #18 | 100 | 4/14/2025 |
| Try #17 | 100 | 4/14/2025 |
| Try #16 | 100 | 4/14/2025 |
| Try #15 | 100 | 4/14/2025 |
| Try #14 | 100 | 4/14/2025 |
| Try #13 | 100 | 4/13/2025 |
| Try #12 | 45 | 4/13/2025 |
| Try #11 | 45 | 4/13/2025 |
| Try #10 | 100 | 4/13/2025 |
| Try #9 | 100 | 4/13/2025 |
| Try #8 | 100 | 4/13/2025 |
| Try #7 | 100 | 4/13/2025 |
| Try #6 | 45 | 4/13/2025 |
| Try #5 | 30 | 4/13/2025 |
| Try #4 | 90 | 4/13/2025 |
| Try #3 | 100 | 4/13/2025 |
| Try #2 | 100 | 4/13/2025 |
| Try #1 | 100 | 4/13/2025 |