Problem Statement
You are given a set of n
cities and a distance matrix dist[][]
, where dist[i][j]
represents the cost to travel from city i
to city j
.
Your task is to:
- Start from city
0
. - Visit every city exactly once.
- Return back to city
0
. - And find the minimum total travel cost.
Examples
Example 1:
Input:
N = 4
dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
Output:
80
Explanation: One of the optimal paths: 0 → 1 → 3 → 2 → 0
Cost = 10 + 25 + 30 + 15 = 80
Different Approaches
1️⃣ Brute Force Approach (Generate All Permutations)