Someone help me please. I have tested with some testcases but I didn’t get accepted on SPOJ. My code is below. Thank you in advance and sorry for my bad english writing skill.
#include <stdio.h>
#include <string.h>
using namespace std;
#define CITY_MAX_NUMBER 1010
#define CONNECTION_MAX_NUMBER 10010
#define NAME_MAX_LENGTH 15
#define PATH_MAX_LENGTH 30
#define PATH_MAX_NUMBER 110
char city_name[CITY_MAX_NUMBER][NAME_MAX_LENGTH];
short path_ends[PATH_MAX_NUMBER][2];
//short tc[PATH_MAX_NUMBER];
short convert_city_name_to_id(int n, char* name);
void swap_values(int x, int y, int* heap, short* heap_pointer, short* city_pointer);
int get_smallest_from_heap(int* heap, int& heap_length, short* heap_pointer, short* city_pointer, short& city_id);
void down_heap(int position, int* heap, int heap_length, short* heap_pointer, short* city_pointer);
void up_heap(int position, int* heap, short* heap_pointer, short* city_pointer);
void add_value_to_heap(int additional_value, int* heap, int& heap_length, short* heap_pointer, short* city_pointer, int city_id);
void alter_value_in_heap(int* heap, int position, int alter_value, short* heap_pointer, short* city_pointer);
void update_path_ends(int n, short path_id, char* input_path);
void find_path(int n, short path_id, int* adjacent_indices, short* adjacent_cities,
int* con_weights, int* dheap, short* dheap_pointer, short* city_pointer);
int main(int argc, char **argv)
{
// printf("hello world\n");
int* adjacent_indices = new int[CITY_MAX_NUMBER];
short* adjacent_cities = new short[CONNECTION_MAX_NUMBER];
int* con_weights = new int[CONNECTION_MAX_NUMBER];
int* dheap = new int[CITY_MAX_NUMBER];
short* city_pointer = new short[CITY_MAX_NUMBER];
short* dheap_pointer = new short[CITY_MAX_NUMBER];
//int* weigh_results = new int[CITY_MAX_NUMBER];
char* input_path = new char[PATH_MAX_LENGTH];
int s, n, r;
scanf("%d", &s);
int i = 0, j, k, previous_p, current_p, temp_length;
short temp_node_id;
while (i < s)
{
scanf("%d\n", &n);
for (j = 0; j < n; j++)
{
memset(city_name[j], 0, NAME_MAX_LENGTH);
fgets(city_name[j], NAME_MAX_LENGTH, stdin);
temp_length = strlen(city_name[j]);
if (city_name[j][temp_length - 1] == '\n')
{
temp_length--;
city_name[j][temp_length] = 0;
}
scanf("%d", ¤t_p);
if (j == 0)
{
adjacent_indices[j] = 0;
} else
{
adjacent_indices[j] = adjacent_indices[j - 1] + previous_p;
}
previous_p = current_p;
for (k = 0; k < current_p; k++)
{
scanf("%hi", &temp_node_id);
//printf("%d", temp_node_id);
adjacent_cities[adjacent_indices[j] + k] = temp_node_id - 1;
scanf("%d\n", &con_weights[adjacent_indices[j] + k]);
}
}
adjacent_indices[n] = adjacent_indices[n - 1] + previous_p;
scanf("%d\n", &r);
//printf("hello\n");
for (k = 0; k < r; k++)
{
memset(input_path, 0, PATH_MAX_LENGTH);
fgets(input_path, PATH_MAX_LENGTH, stdin);
update_path_ends(n, k, input_path);
//printf("%hi %hi\n", path_ends[k][0], path_ends[k][1]);
}
fgets(input_path, PATH_MAX_LENGTH, stdin);
for (k = 0; k < r; k++)
{
find_path(n, k, adjacent_indices, adjacent_cities, con_weights, dheap, dheap_pointer, city_pointer);
}
i++;
}
delete[] adjacent_indices;
delete[] adjacent_cities;
delete[] con_weights;
delete[] dheap;
delete[] dheap_pointer;
delete[] city_pointer;
//delete[] weigh_results;
return 0;
}
short convert_city_name_to_id(int n, char* name)
{
for (int i = 0; i < n; i++)
{
if (strcmp(city_name[i], name) == 0)
{
return i;
}
}
return -1;
}
void update_path_ends(int n, short path_id, char* input_path)
{
int input_length = strlen(input_path);
int i = 0, j = 0, k = 0, end_id;
char* temp_name = new char[NAME_MAX_LENGTH];
while (i < input_length)
{
if (input_path[i] == ' ' || input_path[i] == '\n' || input_path[i] == 0)
{
temp_name[j] = 0;
end_id = convert_city_name_to_id(n, temp_name);
if (end_id >= 0)
{
path_ends[path_id][k] = end_id;
k++;
}
j = 0;
i++;
continue;
}
temp_name[j] = input_path[i];
j++;
i++;
}
delete[] temp_name;
}
void swap_values(int x, int y, int* heap, short* heap_pointer, short* city_pointer)
{
int temp = heap[x];
heap[x] = heap[y];
heap[y] = temp;
city_pointer[heap_pointer[x]] = y;
city_pointer[heap_pointer[y]] = x;
short temp1 = heap_pointer[x];
heap_pointer[x] = heap_pointer[y];
heap_pointer[y] = temp1;
}
void down_heap(int position, int* heap, int heap_length, short* heap_pointer, short* city_pointer)
{
int min_position = position;
int tempID = 2 * position;
for (int i = 0; i < 2; i++)
{
tempID = tempID + i;
if (tempID <= heap_length)
{
if (heap[min_position] > heap[tempID])
{
min_position = tempID;
}
}
}
if (min_position == position)
{
return;
}
swap_values(position, min_position, heap, heap_pointer, city_pointer);
down_heap(min_position, heap, heap_length, heap_pointer, city_pointer);
}
void up_heap(int position, int* heap, short* heap_pointer, short* city_pointer)
{
int parentID;
while (position != 0)
{
parentID = position / 2;
if (heap[parentID] > heap[position])
{
swap_values(parentID, position, heap, heap_pointer, city_pointer);
}
else
{
return;
}
position = parentID;
}
}
int get_smallest_from_heap(int* heap, int& heap_length, short* heap_pointer, short* city_pointer, short& city_id)
{
int temp_result = heap[0];
city_id = heap_pointer[0];
heap[0] = heap[heap_length];
city_pointer[heap_pointer[0]] = -2;
if (heap_length == 0)
{
heap_length = -1;
return temp_result;
}
city_pointer[heap_pointer[heap_length]] = 0;
heap_pointer[0] = heap_pointer[heap_length];
heap_length--;
down_heap(0, heap, heap_length, heap_pointer, city_pointer);
return temp_result;
}
void add_value_to_heap(int additional_value, int* heap, int& heap_length, short* heap_pointer, short* city_pointer, int city_id)
{
heap_length++;
heap[heap_length] = additional_value;
city_pointer[city_id] = heap_length;
heap_pointer[heap_length] = city_id;
up_heap(heap_length, heap, heap_pointer, city_pointer);
}
void alter_value_in_heap(int* heap, int position, int alter_value, short* heap_pointer, short* city_pointer)
{
heap[position] = alter_value;
up_heap(position, heap, heap_pointer, city_pointer);
}
void find_path(int n, short path_id, int* adjacent_indices, short* adjacent_cities, int* con_weights,
int* dheap, short* dheap_pointer, short* city_pointer)
{
int dheap_length = -1;
for (int i = 0; i < n; i++)
{
city_pointer[i] = -1;
}
short temp_destination = path_ends[path_id][0];
add_value_to_heap(0, dheap, dheap_length, dheap_pointer, city_pointer, path_ends[path_id][0]);
int temp_weight1, temp_weight2, i, temp_cityID;
while (temp_destination != path_ends[path_id][1])
{
if (dheap_length == -1)
{
break;
}
temp_weight1 = get_smallest_from_heap(dheap, dheap_length, dheap_pointer, city_pointer, temp_destination);
if (temp_destination == path_ends[path_id][1])
{
break;
}
for (i = adjacent_indices[temp_destination]; i < adjacent_indices[temp_destination + 1]; i++)
{
temp_cityID = adjacent_cities[i];
if (city_pointer[temp_cityID] == -2)
{
continue;
}
temp_weight2 = temp_weight1 + con_weights[i];
if (city_pointer[temp_cityID] >= 0)
{
if (temp_weight2 < dheap[city_pointer[temp_cityID]])
{
alter_value_in_heap(dheap, city_pointer[temp_cityID], temp_weight2, dheap_pointer, city_pointer);
}
continue;
}
if (city_pointer[temp_cityID] == -1)
{
add_value_to_heap(temp_weight2, dheap, dheap_length, dheap_pointer, city_pointer, temp_cityID);
}
}
}
if (temp_destination == path_ends[path_id][1])
{
printf("%d\n", temp_weight1);
}
else
{
printf("0\n");
}
}