ZJU-PAT-Data-Structure-Source-code.rar_PAT test_PAT答案_PAT题集_浙大zi

#include <stdio.h> #include <stdlib.h> #include <string.h> #define error(str) (fprintf(stderr, "%s\n", str)) #define fatal_error(str) (fprintf(stderr, "%s\n", str), exit( 1 )) #define true 1 #define false 0 #define MAX_DISTANCE 250000 #define NOT_VERTEX 500 typedef int elementtype; typedef int vertex; struct listnode; typedef struct listnode *ptrtonode; typedef ptrtonode list; typedef list position; struct listnode { vertex avertex; elementtype weight; ptrtonode next; }; struct table_entry { list lists; int known; int prev_node; int distance; }; struct graph_struct; typedef struct graph_struct *graph; struct graph_struct { int size; struct table_entry *tables; }; void delete_list(list l); list create_list(void); int is_empty(list l); int is_last(position p, list l); void insert(elementtype weight, vertex avertex, list l, position p); position advance(position p); position first(list l); graph create_graph(int size); void destroy_graph(graph g); void add_edge(vertex city_one, vertex city_two, elementtype distance, graph g); static position create_node() { position p; p = malloc(sizeof(struct listnode)); if (p == NULL) { fatal_error("Out of space\n"); } return p; } list create_list(void) { list l; l = create_node(); l->next = NULL; return l; } void delete_list(list l) { position p = l; position tmp; while (p != NULL) { tmp = p; p = advance(p); free(tmp); } } int is_empty(list l) { return l->next == NULL; } int is_last(position p, list l) { return p->next == NULL; } void insert(elementtype weight, vertex avertex, list l, position p) { ptrtonode newnode; newnode = create_node(); newnode->weight = weight; newnode->avertex = avertex; newnode->next = p->next; p->next = newnode; } position advance(position p) { return p->next; } position first(list l) { return l->next; } graph create_graph(int size) { graph g; int i; g = (graph)malloc(sizeof(struct graph_struct)); if (g == NULL) { fatal_error("Out of space\n"); } g->size = size; g->tables = (struct table_entry *)malloc(sizeof(struct table_entry) * size); if (g->tables == NULL) { fatal_error("Out of space\n"); } for (i = 0; i < size; i++) { g->tables[i].lists = create_list(); g->tables[i].known = false; g->tables[i].prev_node = NOT_VERTEX; g->tables[i].distance = MAX_DISTANCE; } return g; } void destroy_graph(graph g) { int i; if (g != NULL) { for (i = 0; i < g->size; i++) { delete_list(g->tables[i].lists); } free(g->tables); free(g); } } void add_edge(vertex city_one, vertex city_two, elementtype distance, graph g) { insert(distance, city_two, g->tables[city_one].lists, g->tables[city_one].lists); insert(distance, city_one, g->tables[city_two].lists, g->tables[city_two].lists); } int *input_rescue(int city_count) { int i; int *rescue_count; rescue_count = (int *)malloc(sizeof(int) * city_count); if (rescue_count == NULL) { fatal_error("Out of space\n"); } for(i = 0; i < city_count; i++) { scanf("%d", &rescue_count[i]); } return rescue_count; } graph input_graph(int city_count, int road_count) { int i; int city_one; int city_two; int distance; graph g; g = create_graph(city_count); for (i = 0; i < road_count; i++) { scanf("%d %d %d", &city_one, &city_two, &distance); add_edge(city_one, city_two, distance, g); } return g; } vertex get_smallest_vertex(graph g) { int i; vertex small; small = NOT_VERTEX; for (i = 0; i < g->size; i++) { if (g->tables[i].known) { continue; } else { if (small == NOT_VERTEX || g->tables[i].distance < g->tables[small].distance) { small = i; } } } return small; } void calc_shorttest_path(graph g, int source_city, int destin_city, int *rescue_count, int *rescue_max, int *path_count) { vertex small_vertex; position adjace; struct table_entry *small_entry; struct table_entry *adjace_entry; int *rescue_per_city; int *path_per_city; rescue_per_city = (int *)malloc(sizeof(int) * g->size); if (rescue_per_city == NULL) { fatal_error("Out of space\n"); } memset(rescue_per_city, 0, sizeof(int) * g->size); path_per_city = (int *)malloc(sizeof(int) * g->size); if (path_per_city == NULL) { fatal_error("Out of space\n"); } memset(path_per_city, 0, sizeof(int) * g->size); g->tables[source_city].distance = 0; rescue_per_city[source_city] = rescue_count[source_city]; path_per_city[source_city] = 1; while ((small_vertex = get_smallest_vertex(g)) != NOT_VERTEX) { small_entry = &g->tables[small_vertex]; small_entry->known = true; adjace = first(small_entry->lists); while (adjace != NULL) { adjace_entry = &g->tables[adjace->avertex]; if (!adjace_entry->known) { if (small_entry->distance + adjace->weight < adjace_entry->distance) { adjace_entry->distance = small_entry->distance + adjace->weight; adjace_entry->prev_node = small_vertex; path_per_city[adjace->avertex] = path_per_city[small_vertex]; rescue_per_city[adjace->avertex] = rescue_per_city[small_vertex] + rescue_count[adjace->avertex]; } else if (small_entry->distance + adjace->weight == adjace_entry->distance) { path_per_city[adjace->avertex] += path_per_city[small_vertex]; if (rescue_per_city[adjace->avertex] < rescue_per_city[small_vertex] + rescue_count[adjace->avertex]) { rescue_per_city[adjace->avertex] = rescue_per_city[small_vertex] + rescue_count[adjace->avertex]; adjace_entry->prev_node = small_vertex; } } } adjace = advance(adjace); } } *rescue_max = rescue_per_city[destin_city]; *path_count = path_per_city[destin_city]; free(rescue_per_city); free(path_per_city); } void print_path(graph g, int destin_city) { if (g->tables[destin_city].prev_node != NOT_VERTEX) { print_path(g, g->tables[destin_city].prev_node); printf(" "); } printf("%d", destin_city); } int main(void) { int city_count; int road_count; int source_city; int destin_city; int rescue_max; int path_count; int *rescue_count; graph g; scanf("%d %d %d %d", &city_count, &road_count, &source_city, &destin_city); rescue_count = input_rescue(city_count); g = input_graph(city_count, road_count); calc_shorttest_path(g, source_city, destin_city, rescue_count, &rescue_max, &path_count); printf("%d %d\n", path_count, rescue_max); print_path(g, destin_city); free(rescue_count); destroy_graph(g); return 0; }