How To Make Code Easy, Understandable And Good Accuracy?

general
, , , , , , , , ,
1

Problem: Traveling Salesman Problem with Time Windows (TSP-TW)

Problem Statement:

You are given a set of N cities (2 ≤ N ≤ 20).

  • You start at city 1 at time 0.
  • Each city i has a time window [L[i], R[i]] — you must arrive at city i within this window.
  • You can travel between cities i and j in time T[i][j].
  • Each city must be visited exactly once, and you return to city 1.

Goal:

  • Find the minimum total travel time while respecting all time windows.
  • If it is impossible, return -1.

Input Format:

N
L1 R1
L2 R2
...
LN RN
T[1][1] T[1][2] ... T[1][N]
T[2][1] T[2][2] ... T[2][N]
...
T[N][1] T[N][2] ... T[N][N]
  • 1 ≤ N ≤ 20
  • 0 ≤ Li ≤ Ri ≤ 10^9
  • 0 ≤ T[i][j] ≤ 10^6

Output Format:

Minimum travel time satisfying all time windows

or -1 if impossible.

Example:

Input:

4
0 10
2 15
5 20
8 25
0 3 6 7
3 0 2 4
6 2 0 3
7 4 3 0

Output:

17