# 13800 - TSP Logistics
>author: Utin
###### tags: `recursion`

---

## Brief
See the code below

## Solution 0

#include <string.h>
#define P_NUM 13

typedef struct place place;
typedef struct roads roads;

struct roads {
    int length;       // The length of the route
    place *place;     // Point to the end of the route
};

struct place { 
    int id;           // Index of place, 0 represents the cargo center, and 1~n represents the stores
    int demand;       // Each store has specific units of goods that are demanded to deliver.
    int numOfRoads;   // The number of places which has a road connected to it
    roads roads[P_NUM];
};

long long dp[P_NUM][31][1<<P_NUM];
long long gph[P_NUM][P_NUM];

long long min(long long a, long long b) {
    if (a < b) return a;
    else return b;
}

// Floyd–Warshall algorithm (DP)
void distance(place *p, int n) {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            gph[i][j] = 1e15;
        }
    }
    // 將題目的條件放進gph
    for (int i=0; i<n; i++) {
        gph[i][i] = 0;
        for (int j=0; j<(p+i)->numOfRoads; j++) {
            gph[i][(p+i)->roads[j].place->id] = (p+i)->roads[j].length;
        }
    }
    // 取最短距離
    for (int k=0; k<n; k++) {
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                // 向量和：ik + kj == ij
                gph[i][j] = min(gph[i][j], gph[i][k]+gph[k][j]);
            }
        }
    }
}

long long int solve(place* center, int n, int curr, int goods, int visited) {
    if (dp[curr][goods][visited] != -1) return dp[curr][goods][visited];
    // final step: 送完要回center
    if (visited == (1<<n)-1) return dp[curr][goods][visited] = gph[curr][0];

    long long int ans = 1e15;
    for (int i = 1; i < n; i++) {
        if (visited & (1<<i)) continue;

        if ((center+i)->demand <= goods) {
            ans = min(ans, gph[curr][i] + solve(center, n, i, goods-(center+i)->demand, visited | (1<<i)));
        }
        // 每次都必須跟回center補貨的狀況比較一次
        ans = min(ans, gph[curr][0] + gph[0][i] + solve(center, n, i, 30-(center+i)->demand, visited | (1<<i)));
    }
    return dp[curr][goods][visited] = ans;
}

long long minRoute(place *p, int n) {
    distance(p, n);
    memset(dp, -1, sizeof(dp));
    return solve(p, n, 0, 30, 1);
}

// By Utin

## Reference