Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stddef.h>
- #include <string.h>
- #include <stdlib.h>
- #include <stdio.h>
- #include <limits.h>
- #define MAX_CITIES 10
- struct route;
- struct city
- {
- char name[16];
- struct route* routes;
- };
- struct city* add_city(struct city** cities, const char* name, size_t maxcount)
- {
- struct city* c;
- while (*cities && maxcount--)
- cities++;
- if (!maxcount) return NULL;
- c = *cities = calloc(1, sizeof **cities);
- if (c) strcpy(c->name, name);
- return c;
- }
- struct city* find_city(struct city** cities, const char* name)
- {
- while (*cities)
- {
- if (strcmp((*cities)->name, name) == 0)
- return *cities;
- ++cities;
- }
- return NULL;
- }
- struct city* find_or_add_city(struct city** cities, const char* name, size_t maxcount)
- {
- struct city* c;
- if ((c = find_city(cities, name)) == NULL)
- c = add_city(cities, name, maxcount);
- return c;
- }
- struct route
- {
- struct city* to;
- unsigned distance;
- struct route* next;
- };
- void do_add_route(struct city* from, struct city* to, unsigned distance)
- {
- struct route* rte = from->routes,
- * newrte = calloc(1, sizeof *newrte);
- if (!newrte)
- {
- perror("can't create route");
- exit(EXIT_FAILURE);
- }
- newrte->to = to;
- newrte->distance = distance;
- if (!rte)
- from->routes = newrte;
- else
- {
- while (rte->next)
- rte = rte->next;
- rte->next = newrte;
- }
- }
- void add_route(struct city* from, struct city* to, unsigned distance)
- {
- do_add_route(from, to, distance);
- do_add_route(to, from, distance);
- }
- int parse_input(FILE* stream, struct city** cities, size_t maxcount)
- {
- size_t i = 0;
- while (i < maxcount && !feof(stream))
- {
- char from[16], to[16];
- unsigned distance;
- struct city* fromcity,
- * tocity;
- int parse_status = scanf("%15s to %15s = %u\n", from, to, &distance);
- if (parse_status != 3)
- {
- char garbage[21];
- if (ferror(stream))
- perror("can't read input");
- else
- {
- fgets(garbage, 20, stream);
- fprintf(stderr, "parse error near '%s'\n", garbage);
- }
- return 0;
- }
- fromcity = find_or_add_city(cities, from, maxcount);
- if (!fromcity)
- {
- fprintf(stderr, "could not add city '%s'\n", from);
- return 0;
- }
- tocity = find_or_add_city(cities, to, maxcount);
- if (!tocity)
- {
- fprintf(stderr, "could not add city '%s'\n", to);
- return 0;
- }
- add_route(fromcity, tocity, distance);
- }
- return 1;
- }
- unsigned distance_to(struct city* c, const char* name)
- {
- struct route* rte = c->routes;
- while (rte)
- {
- if (strcmp(rte->to->name, name) == 0)
- return rte->distance;
- rte = rte->next;
- }
- return 0;
- }
- unsigned measure_route(struct city** cities)
- {
- unsigned distance = 0;
- while (cities[1])
- {
- unsigned leg = distance_to(cities[0], cities[1]->name);
- if (!leg)
- /* hit a dead end */
- return 0;
- distance += leg;
- ++cities;
- }
- return distance;
- }
- void print_route(struct city** cities)
- {
- while (*cities)
- {
- struct city* c = *cities;
- printf("%s ", c->name);
- if (*++cities)
- fputs("-> ", stdout);
- }
- }
- void swap_cities(struct city** left, struct city** right)
- {
- struct city* mid = *left;
- *left = *right;
- *right = mid;
- }
- void try_route(struct city** cities, unsigned* shortest, unsigned* longest)
- {
- unsigned distance = measure_route(cities);
- if (!distance)
- /* can't get here from there */
- return;
- /*print_route(cities);
- printf("= %u", distance);*/
- if (distance < *shortest)
- {
- *shortest = distance;
- fputs("New shortest: ", stdout);
- print_route(cities);
- printf("= %u\n", distance);
- /*putchar('*');*/
- }
- if (distance > *longest)
- {
- *longest = distance;
- fputs("New longest: ", stdout);
- print_route(cities);
- printf("= %u\n", distance);
- }
- /*putchar('\n');*/
- }
- void try_routes(struct city** cities, size_t count, unsigned* shortest, unsigned* longest)
- {
- size_t i;
- if (count == 1)
- try_route(cities, shortest, longest);
- else
- {
- for (i = 0; i < count - 1; ++i)
- {
- try_routes(cities, count - 1, shortest, longest);
- if ((count & 1) == 0)
- swap_cities(cities + i, cities + (count - 1));
- else
- swap_cities(cities, cities + (count - 1));
- }
- try_routes(cities, count - 1, shortest, longest);
- }
- }
- int main(void)
- {
- struct city* cities[MAX_CITIES + 1] = {0};
- unsigned shortest = UINT_MAX, longest = 0;
- size_t count = 0;
- if (!parse_input(stdin, cities, MAX_CITIES))
- return EXIT_FAILURE;
- while (cities[count])
- ++count;
- try_routes(cities, count, &shortest, &longest);
- printf("The shortest distance is %u\n"
- "The longest distance is %u\n",
- shortest, longest);
- return EXIT_SUCCESS;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement