#include <stdio.h>

int fuel_city[4][4] = { 0 };

/*
 * travelcity() should just calculate the travel length
 * and modify the values passed from the main() function via pointers.
 *
 * No printings should be done.
 */
          /* typo : int *dst  // dst is not passed as pointer */
void travelcity(int *state, int dst, int *remain);

int main()
{
    int move_dist = 0, remain_fuel = 400;
    int current_pos = 1, dest = 0;

    for (int i = 0; i < 3; i++) {
        for (int j = 1; j < 4; j++) {
            if (i < j) {
                printf
                    ("Please input fuel cost between #%d city to #%d city\n",
                     i + 1, j + 1);
                scanf("%d", &fuel_city[i][j]);

                // Array is half-filled diagnoally, fill the rest
                fuel_city[j][i] = fuel_city[i][j];
            }
        }
    }

    while (remain_fuel > 0) {
        printf("Please input the city to travel\n");
        scanf("%d", &dest);

        if (dest != -1) {
            if (current_pos != dest && dest < 5) {
                // Common print whether remain_fuel is > 0 or not
                printf("The car start from city #%d, ",
                       current_pos);

                travelcity(&current_pos, dest, &remain_fuel);
            } else {
                printf("Please input correct # of city.\n\n");

                // Go loop again
                continue;
            }

            if (remain_fuel > 0) {
                printf
                    ("The car arrive in city #%d, "
                     "and remain fuel is %d\n", dest,
                     remain_fuel);
            } else {
                printf
                    ("The car stopped before reaching the #%d city, "
                     "remain fuel is 0, The travel is end.\n",
                     dest);
            }
        } else {
            printf("remain fuel is %d, The travel is end.\n",
                   remain_fuel);
            break;
        }
    }

    return 0;
}

void travelcity(int *state, int dst, int *remain)
{
// "Extension Goal" : To disable "Extension Goal" feature, comment from here
    int first_waypoint = 0;
    int second_waypoint = 0;
    int third_waypoint = 0;

    int total_fuel = fuel_city[*state - 1][dst - 1];
    // "from" -> i -> j -> k -> "to"
    // Calculate the most efficient route
    for (int i = 1; i < 5; i++) {
        if (*state == i)    // No movement needed
            continue;
        for (int j = 1; j < 5; j++) {
            if (i == j) // No movement needed
                continue;
            for (int k = 1; k < 5; k++) {
                int tmp = fuel_city[*state - 1][i - 1]  // "from" -> i
                        + fuel_city[i - 1][j - 1]   // i -> j
                        + fuel_city[j - 1][k - 1]   // j -> k
                        + fuel_city[k - 1][dst - 1];    // k -> dst

                if (tmp < total_fuel) {
                    // More efficient than previous iteration
                    first_waypoint = i;
                    second_waypoint = j;
                    third_waypoint = k;

                    total_fuel = tmp;
                }
            }
        }
    }

    if (total_fuel < fuel_city[*state - 1][dst - 1]) {
        // Fuel can be saved by visiting waypoint(s)

        if (*state != first_waypoint && first_waypoint != dst) {
            printf("first waypoint city : #%d, ", first_waypoint);

            // Travel to the waypoint
            travelcity(state, first_waypoint, remain);
        }

        if (first_waypoint != second_waypoint &&
            second_waypoint != third_waypoint &&
            second_waypoint != dst) {
            printf("second waypoint city : #%d, ", second_waypoint);

            // Travel to the waypoint
            travelcity(state, second_waypoint, remain);
        }

        if (second_waypoint != third_waypoint && third_waypoint != dst) {
            printf("third waypoint city : #%d, ", third_waypoint);

            // Travel to the waypoint
            travelcity(state, third_waypoint, remain);
        }
        // Travel to the final destination
        travelcity(state, dst, remain);

        printf("\n");
    } else {
// "Extension Goal" : to here
        // Direct route is the most efficient
        if (*remain < fuel_city[*state - 1][dst - 1]) {
            // Insufficient fuel
            *remain = 0;
        } else {
            // Travel done, "to" is now the new "from"
            *remain -= fuel_city[*state - 1][dst - 1];
            *state = dst;
        }
// "Extension Goal" : and remove this bracket
    }
}