Short Path
There is an ancient saying that "All Roads Lead to Rome". If this were true, then there is a simple algorithm for finding a path between any two cities. To go from city A to city B, a traveller could take a road from A to Rome, then from Rome to B. Of course, a shorter route may exist. The network of roads in the Roman Empire had a simple structure: beginning at Rome, a number of roads extended to the nearby cities. From these cities, more roads extended to the next further cities, and so on. Thus, the cities could be thought of as existing in levels around Rome, with cities in the ith level only connected to cities in the i - 1th and i + 1th levels (Rome was considered to be at level 0). No loops existed in the road network. Any city in level i was connected to a single city in level i - 1, but was connected to zero or more cities in level i+1. Thus, to get to Rome from a given city in level i, a traveller could simply walk along the single road leading to the connected i - 1 level city, and repeat this process, with each step getting closer to Rome. Given a network of roads and cities, your task is to find the shortest route between any two given cities, where distance is measured in the number of intervening cities.
Input
The first line is the number of test cases, followed by a blank line. The first line of each test case of the input contains two numbers in decimal notation separated by a single space. The first number (m) is the number of roads in the road network to be considered. The second number (n) represents the number of queries to follow later in the file. For each test case, in the next m lines in the input each contain the names of a pair of cities separated by a single space. A city name consists of one or more letters, the first of which is in uppercase. No two cities begin with the same letter. The name Rome always appears at least once in this section of input, for each test case; this city is considered to be at level 0, the lowest-numbered level. The pairs of names indicate that a road connects the two named cities. The first city named on a line exists in a lower level than the second named city. The road structure obeys the rules described above. For each test case, no two lines of input in this section are repeated. The next n lines, for each test case in the input each contain the names of a pair of cities separated by a single space. City names are as described above. These pairs of cities are the query pairs. Your task for each query pair is to find the shortest route from the first named city to the second. Each of the cities in a query pair is guaranteed to have appeared somewhere in the previous input section, for each test case, describing the road structure. Each test case will be separated by a single line.
Q1: 輸入與輸出說明 • 輸入的第一列是測試資料的組數。每組測試資料的第一列有 兩個整數m及n,分別表示道路的數量(m)及要查詢的次數(n)。 • m列道路資訊,表示有道路相連的兩个城市，前面的城市(level 數字較小)較接近羅馬；接下來有n 列，每列有兩個城市，則 必需回答這兩個城市之間的最短路徑走法。 • 輸入的各個城市的字首不重複。比如： • Rome以R表示，Turin以T表示，Venice以V表示，Gamyo G， Pisa是P，Florence是F，Athens是A，Mila是M。要輸出兩城市 間最短路徑走法時，只要依序輸出經過的城市字首即可。 • 舉列來說：Turin到pisa的走法，最短路徑是由Turin經Rome再 到Pisa，就輸出TRP • Milan到Florence 會依序經過Milan、Turin、Rome、Pisa、 Florece,所以輸出MTRPFㆍ • Athens 到Genoa 會依序經過Athens 、Venice、Turin、Genoa， 所以輸出AVTG • Note: 不同組的測試資料之間必須用空白行隔開。
In each test case, for each of the n query pairs, output a sequence of uppercase letters indicating the shortest route between the two query pair cities. The sequence must be output as consecutive letters, without intervening whitespace, on a single line. For each test case, the first output line corresponds to the first query pair, the second output line corresponds to the second query pair, and so on. The letters in each sequence indicate the first letter of the cities on the desired route between the query pair cities, including the query pair cities themselves. A city will never be paired with itself in a query. Print a blank line between the outputs for two consecutive test cases.
Sample Input 1
1
7 3
Rome Turin
Turin Venice
Turin Genoa
Rome Pisa
Pisa Florence
Venice Athens
Turin Milan
Turin Pisa
Milan Florence
Athens Genoa
Sample Output 1
TRP
MTRPF
AVTG
HINT: • 因為道路是以羅馬為中心往周邊的城市依序延伸出去的樹狀結構,所以 可以把羅馬當成是樹根(root)。 • 使用陣列來儲存從城市1到羅馬的走法(route1)及城市2到羅馬的走法 (route2)，再將兩條路徑裡重複的部分刪掉。 • 將三組的輸入資料所描述的道路畫成對應的樹狀結構圖，如圖所示。其 中，較粗的箭號代表儲存在陣列裡由各城市到達羅馬的走法。
HINT： • Because the roads are structured like a tree spreading out from Rome to the surrounding cities, Rome can be considered the root of the tree. • Use arrays to store the routes from City 1 to Rome (route1) and from City 2 to Rome (route2), and then delete the parts that are repeated in both routes. • Draw the corresponding tree diagrams for the three sets of input data describing the roads as shown in the figure. In the diagrams, the thicker arrows represent the routes stored in the arrays from each city to Rome.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CITIES 100
#define MAX_NAME_LENGTH 11
struct Node {
char city[MAX_NAME_LENGTH];
struct Node* parent;
};
void print_route(struct Node* city) {
if (city->parent != NULL) {
print_route(city->parent);
}
printf("%c", city->city[0]);
}
void find_shortest_route(struct Node* graph[MAX_CITIES], int m, int n, const char* start, const char* end) {
struct Node* route1[MAX_CITIES] = {NULL};
struct Node* route2[MAX_CITIES] = {NULL};
// Find route from start to Rome (root)
struct Node* current = graph[start[0] - 'A'];
int i = 0;
while (current != NULL) {
route1[i] = current;
current = current->parent;
i++;
}
// Find route from end to Rome (root)
current = graph[end[0] - 'A'];
int j = 0;
while (current != NULL) {
route2[j] = current;
current = current->parent;
j++;
}
// Find common part in the routes
int commonIndex = 0;
while (route1[i - 1 - commonIndex] == route2[j - 1 - commonIndex]) {
commonIndex++;
}
// Print the route from start to Rome
for (int k = 0; k < i - commonIndex; k++) {
printf("%c", route1[k]->city[0]);
}
// Print the route from Rome to end (excluding the common part)
for (int k = j - commonIndex - 1; k >= 0; k--) {
printf("%c", route2[k]->city[0]);
}
printf("\\n");
}
int main() {
int num_test_cases;
scanf("%d", &num_test_cases);
for (int t = 0; t < num_test_cases; t++) {
if (t > 0) {
printf("\\n");
}
int m, n;
scanf("%d %d", &m, &n);
struct Node* graph[MAX_CITIES] = {NULL};
// Build the graph
for (int i = 0; i < m; ++i) {
char city1[MAX_NAME_LENGTH], city2[MAX_NAME_LENGTH];
scanf("%s %s", city1, city2);
struct Node* newNode1 = (struct Node*)malloc(sizeof(struct Node));
strcpy(newNode1->city, city1);
newNode1->parent = NULL;
graph[city1[0] - 'A'] = newNode1;
struct Node* newNode2 = (struct Node*)malloc(sizeof(struct Node));
strcpy(newNode2->city, city2);
newNode2->parent = newNode1;
graph[city2[0] - 'A'] = newNode2;
}
// Assign correct parent pointers
for (int i = 0; i < MAX_CITIES; ++i) {
if (graph[i] != NULL && graph[i]->parent != NULL) {
graph[i]->parent = graph[graph[i]->parent->city[0] - 'A'];
}
}
// Process queries
for (int i = 0; i < n; ++i) {
char start[MAX_NAME_LENGTH], end[MAX_NAME_LENGTH];
scanf("%s %s", start, end);
// Find the shortest route and output the result
find_shortest_route(graph, m, n, start, end);
}
// Free allocated memory
for (int i = 0; i < MAX_CITIES; ++i) {
free(graph[i]);
}
}
return 0;
}
please note the answer is wronf, root isnt added into the calculation. please note, default ans below.
#include<stdio.h>
struct tree{
char name[10];
struct tree *next[5];
};
void TreeForward(char forward[10],char arr1[10],int *count,tree *data,bool *a){
if(forward[0]==data->name[0]){
arr1[(*count)++] = forward[0];
(*a) = true;
return;
}else{
for(int b=0;b<5;b++){
if(data->next[b]!=NULL){
TreeForward(forward,arr1,count,data->next[b],a);
}
if((*a)==true){
arr1[(*count)++]=data->name[0];
return;
}
}
}
}
void serch(tree *data,char ddd[10]){
bool arraysEqual = true;
int count = 0;
while (arraysEqual && data->name[count]!='\\0'){
if (data->name[count] != ddd[count]){
arraysEqual = false;
}
count++;
}
if(arraysEqual==true){
for(int c=0;c<5;c++){
if(data->next[c]==NULL){
data->next[c] = new tree();
data = data->next[c];
scanf("%s",data->name);
break;
}
}
return;
}else{
for(int a=0;a<5;a++){
if(data->next[a]!=NULL){
serch(data->next[a],ddd);
}
}
}
}
int main(void){
int n;
scanf("%d",&n);
for(int a=0;a<n;a++){
int x,y;
scanf("%d %d",&x,&y);
tree *head = new tree();
tree *data = head;
scanf("%s",&head->name);
head->next[0] = new tree();
data = head->next[0];
scanf("%s",&data->name);
for(int b=0;b<x-1;b++){
char ddd[10];
data = head;
scanf("%s",&ddd);
serch(data,ddd);
}
data = head;
for(int b=0;b<y;b++){
char forward[10];
char back[10];
scanf("%s %s",&forward,&back);
char arr1[10];
char arr2[10];
int count=0;
bool TF = false;
TreeForward(forward,arr1,&count,data,&TF);
int count2 = 0;
data = head;
TF = false;
TreeForward(back,arr2,&count2,data,&TF);
data = head;
TF = false;
bool end = false;
for(int b=0;b<count;b++){
printf("%c",arr1[b]);
for(int c=count2-1;c>=0;c--){
if(arr1[b]==arr2[c]){
for(int f = c-1;f>=0;f--){
printf("%c",arr2[f]);
}
printf("\\n");
end = true;
}
if(end == true){
break;
}
}
if(end == true){
break;
}
}
}
printf("\\n");
}
}
Description
Input
