#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MaxNum 10
#define INFINITY 9999
#define MaxStringLength 100
 
typedef struct GNode {
    int NumVertex;
    int NumEdge;
    int Vertexs[MaxNum][MaxNum];
    char VertexData[MaxNum][MaxStringLength];
} Graph;
 
typedef struct view{
	char viewname[100];
	char viewinformation[1000];
}view;
void enter(view v[],char*name,char*information,int i){
		strcpy(v[i].viewname,name);
		strcpy(v[i].viewinformation,information);
}
void print_view(view v[]){
	for(int i=0;i<10;i++){
		printf("景点名称：%s\n",v[i].viewname);
		printf("景点介绍：%s\n",v[i].viewinformation);
		printf("\n");
	}
}
void visit(Graph* graph, int vertex) {
    printf("%s ", graph->VertexData[vertex]);
}
 
Graph* Make_Graph(int NumVertex, int NumEdge) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->NumVertex = NumVertex;
    graph->NumEdge = 0;
    for (int i = 0; i < NumVertex; i++) {
        for (int j = 0; j < NumVertex; j++) {
            graph->Vertexs[i][j] = 0;
        }
    }
    return graph;
}
 
void Add_Edge(Graph* graph, int vertex1, int vertex2, int weight) {
    if (graph == NULL || graph->NumVertex == 0) {
        printf("error");
        return;
    }
    graph->Vertexs[vertex1][vertex2] = weight;
    graph->Vertexs[vertex2][vertex1] = weight;
}
 
void Add_Vertex_Data(Graph* graph, int vertex, char* name) {
    if (graph == NULL || vertex > graph->NumVertex - 1 || vertex < 0) {
        printf("error");
        return;
    }
    strcpy(graph->VertexData[vertex], name);
}
 
void DFS(Graph* graph, int vertex, void (*visit)(Graph*, int), bool visited[]) {
    visit(graph, vertex);
    visited[vertex] = true;
    for (int i = 0; i < graph->NumVertex; i++) {
        if (graph->Vertexs[vertex][i] != 0 && !visited[i] && graph->Vertexs[vertex][i] != INFINITY) {
            DFS(graph, i, visit, visited);
        }
    }
}
 
void dijkstra(Graph* graph, int start, bool visited[]) {
    int T[MaxNum][2];
    for (int i = 0; i < graph->NumVertex; i++) {
        T[i][0] = INFINITY;
        T[i][1] = -1;
        visited[i] = false;
    }
    T[start][0] = 0;
    T[start][1] = -1;
    for (int i = 0; i < graph->NumVertex - 1; i++) {
        int mindist = INFINITY;
        int minindex = -1;
        for (int j = 0; j < graph->NumVertex; j++) {
            if (!visited[j] && T[j][0] < mindist) {
                mindist = T[j][0];
                minindex = j;
            }
        }
        visited[minindex] = true;
        for (int k = 0; k < graph->NumVertex; k++) {
            if (!visited[k] && graph->Vertexs[minindex][k] != 0 && T[minindex][0] + graph->Vertexs[minindex][k] < T[k][0]) {
                T[k][0] = T[minindex][0] + graph->Vertexs[minindex][k];
                T[k][1] = minindex;
            }
        }
    }
    int end;
    printf("请输入目的地编号：");
    scanf("%d", &end);
    printf("最短距离为：%dkm\n", T[end][0]);
    printf("最短路线为：%s ", graph->VertexData[end]);
    int temp = T[end][1];
    while (temp != -1) {
        printf("<- %s ", graph->VertexData[temp]);
        temp = T[temp][1];
    }
}
 
int main() {
    bool visited[MaxNum];
    for (int i = 0; i < MaxNum; i++) {
        visited[i] = false;
    }
    int NumVertex = 10;
    int NumEdge = 19;
    Graph* graph = Make_Graph(NumVertex, NumEdge);
    for (int i = 0; i < NumVertex; i++) {
        char* name = (char*)malloc(sizeof(char) * 100);
        printf("请输入%d号景点的名称：\n", i);
        scanf("%s", name);
        Add_Vertex_Data(graph, i, name);
    }
    for (int i = 0; i < NumEdge; i++) {
        int v1, v2, weight;
        printf("请输入两个景点的编号和距离：\n");
        scanf("%d %d %d", &v1, &v2, &weight);
        printf("从%d号景点到%d号景点的距离%d:\n", v1, v2, weight);
        Add_Edge(graph, v1, v2, weight);
        printf("\n\n");
    };
    view v[10];
    for(int i=0;i<10;i++){
    	char*name=(char*)malloc(sizeof(char)*100);
    	char*information=(char*)malloc(sizeof(char)*1000);
    	printf("请输入景点名称："); 
    	scanf("%s",name);
    	printf("请输入景点信息：");
    	scanf("%s",information);
		enter(v,name,information,i); 
	}
    printf("\n\n");
    int choice;
	int start;
    do{
    	
        printf("                                                                               \n");
        printf("                                                                               \n");                                 
        printf("                  |-------------0殷墟------1袁林-------2中国文字博物馆         \n");
        printf("                  |              |                  |             |            \n");
        printf("6红旗渠------------              |                  |             |            \n");
        printf("    |             |              |---------------4羑里城-----------            \n");
        printf("    |             |              |                  |             |            \n");
        printf("    |             |              |                  |             |            \n");
        printf("7太行大峡谷-------|-------------3长春观----------5岳飞庙-------   |            \n");
        printf("                                                    |         |   |            \n");
        printf("                                                    |          8二帝陵         \n");
        printf("                                                    |             |            \n");
        printf("                                                    |             |            \n");
        printf("                                                    |----------9明福寺         \n");
        printf("                                                                               \n");
        printf("                                                                               \n");
        printf("*******************************河南安阳旅游地图********************************\n");
        printf("                                                                               \n");
    	printf("              【1】景点名称及相关信息\n");
    	printf("              【2】深度遍历景点\n");
		printf("              【3】获取最短路径\n");
		printf("               请输入你的选项：\n");
		scanf("%d",&choice);
		printf("\n\n\n");
		if(choice==1){
			print_view(v);
		} 
		if(choice==2){
			int num;
			printf("请输入作为遍历起点的景点编号：");
			scanf("%d",&num);
			DFS(graph, num, visit, visited);
			printf("\n");
		}
		if(choice==3){
			printf("请输入出发地地点编号：\n");
            scanf("%d", &start);
            dijkstra(graph, start, visited);
            printf("\n");
		}
	}while(choice!=0);
    return 0;
}

殷墟
袁林
文字博物馆
长春观
羑里城
岳飞庙
红旗渠
太行大峡谷
二帝陵
明福寺
0 1 5
0 2 8
0 3 30
0 4 20
0 6 70
1 2 5
1 4 20
2 4 20
2 8 75
3 4 40
3 5 35
3 6 60
3 7 30
4 5 5
4 8 60
5 8 55
5 9 60
6 7 30
8 9 40
殷墟
殷墟，河南安阳的商朝都城遗址，重要考古发现包括甲骨文，推动了中国信史进展。
袁林
袁林，又称袁坟，是清末民初政治家袁世凯的墓地，位于河南省安阳市。墓地规模宏大，建筑风格独特，是近现代重要史迹及代表性建筑。
文字博物馆
中国文字博物馆是一座位于河南省安阳市的*博物馆，以汉字为主题，展示汉字的起源、发展、演变和应用。博物馆旨在收藏、研究、展示和阐释中华优秀语言文化
长春关
河南安阳长春观，道教全真派宫观，历史悠久，明清建筑风格，供奉道教神祇。
羑里城
羑里城，位于河南安阳，是中国最古老的*之一，有“司法博物馆”之称。
岳飞庙
纪念南宋抗金名将岳飞，建筑精美，存有岳飞文物，为爱国主义教育场所。
红旗渠
红旗渠，位于河南林州，是新中国成立后人民自力更生、艰苦奋斗的典范，人工修建的大型灌区，被誉为“人工天河”。
太行大峡谷
太行大峡谷，位于河南林州，是太行山内的壮观峡谷，自然景观丰富，有“奇峰万矗”之美誉，是一处著名的自然风光旅游区。
二帝陵
二帝陵，位于河南省安阳市，是相传中华民族的人文始祖炎帝神农氏和黄帝轩辕氏的陵墓，是中华文明的重要遗迹。
明福寺
明福寺，位于中国河南省安阳市，是一座历史悠久的佛教寺庙，始建于唐代，经历代维修和扩建，寺内保存有珍贵的文物和佛教艺术品，是安阳市的重要佛教文化和历史遗迹。

//读取文件版本
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MaxNum 10
#define INFINITY 9999
#define MaxStringLength 100
 
typedef struct GNode {
    int NumVertex;
    int NumEdge;
    int Vertexs[MaxNum][MaxNum];
    char VertexData[MaxNum][MaxStringLength];
} Graph;
 
typedef struct view{
	char viewname[1000];
	char viewinformation[10000];
}view;
void enter(view v[],char*name,char*information,int i){
		strcpy(v[i].viewname,name);
		strcpy(v[i].viewinformation,information);
}
void print_view(view v[]){
	for(int i=0;i<10;i++){
		printf("景点名称：%s\n",v[i].viewname);
		printf("景点介绍：%s\n",v[i].viewinformation);
		printf("\n");
	}
}

void visit(Graph* graph, int vertex) {
    printf("%s ", graph->VertexData[vertex]);
}
 
Graph* Make_Graph(int NumVertex, int NumEdge) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->NumVertex = NumVertex;
    graph->NumEdge = 0;
    for (int i = 0; i < NumVertex; i++) {
        for (int j = 0; j < NumVertex; j++) {
            graph->Vertexs[i][j] = 0;
        }
    }
    return graph;
}
 
void Add_Edge(Graph* graph, int vertex1, int vertex2, int weight) {
    if (graph == NULL || graph->NumVertex == 0) {
        printf("error");
        return;
    }
    graph->Vertexs[vertex1][vertex2] = weight;
    graph->Vertexs[vertex2][vertex1] = weight;
}
 
void Add_Vertex_Data(Graph* graph, int vertex, char* name) {
    if (graph == NULL || vertex > graph->NumVertex - 1 || vertex < 0) {
        printf("error");
        return;
    }
    strcpy(graph->VertexData[vertex], name);
}
 
void DFS(Graph* graph, int vertex, void (*visit)(Graph*, int), bool visited[]) {
    visit(graph, vertex);
    visited[vertex] = true;
    for (int i = 0; i < graph->NumVertex; i++) {
        if (graph->Vertexs[vertex][i] != 0 && !visited[i] && graph->Vertexs[vertex][i] != INFINITY) {
            DFS(graph, i, visit, visited);
        }
    }
}
 
void dijkstra(Graph* graph, int start, bool visited[]) {
    int T[MaxNum][2];
    for (int i = 0; i < graph->NumVertex; i++) {
        T[i][0] = INFINITY;
        T[i][1] = -1;
        visited[i] = false;
    }
    T[start][0] = 0;
    T[start][1] = -1;
    for (int i = 0; i < graph->NumVertex - 1; i++) {
        int mindist = INFINITY;
        int minindex = -1;
        for (int j = 0; j < graph->NumVertex; j++) {
            if (!visited[j] && T[j][0] < mindist) {
                mindist = T[j][0];
                minindex = j;
            }
        }
        visited[minindex] = true;
        for (int k = 0; k < graph->NumVertex; k++) {
            if (!visited[k] && graph->Vertexs[minindex][k] != 0 && T[minindex][0] + graph->Vertexs[minindex][k] < T[k][0]) {
                T[k][0] = T[minindex][0] + graph->Vertexs[minindex][k];
                T[k][1] = minindex;
            }
        }
    }
    int end;
    printf("请输入目的地编号：");
    scanf("%d", &end);
    printf("最短距离为：%dkm\n", T[end][0]);
    printf("最短路线为：%s ", graph->VertexData[end]);
    int temp = T[end][1];
    while (temp != -1) {
        printf("<- %s ", graph->VertexData[temp]);
        temp = T[temp][1];
    }
}
 
int main() { 
	FILE *fp;
	fp=fopen("data.txt","r");
    bool visited[MaxNum];
    for (int i = 0; i < MaxNum; i++) {
        visited[i] = false;
    }
    int NumVertex = 10;
    int NumEdge = 19;
    Graph* graph = Make_Graph(NumVertex, NumEdge);
    for (int i = 0; i < NumVertex; i++) {
        char* name = (char*)malloc(sizeof(char) * 100);
        printf("请输入%d号景点的名称：\n", i);
        fscanf(fp,"%s", name);
        Add_Vertex_Data(graph, i, name);
    }
    for (int i = 0; i < NumEdge; i++) {
        int v1, v2, weight;
        printf("请输入两个景点的编号和距离：\n");
        fscanf(fp,"%d %d %d", &v1, &v2, &weight);
        printf("从%d号景点到%d号景点的距离%d:\n", v1, v2, weight);
        Add_Edge(graph, v1, v2, weight);
        printf("\n\n");
    };
    view v[10];
    for(int i=0;i<10;i++){
    	char*name=(char*)malloc(sizeof(char)*100);
    	char*information=(char*)malloc(sizeof(char)*1000);
    	printf("请输入景点名称："); 
    	fscanf(fp,"%s",name);
    	printf("请输入景点信息：");
    	fscanf(fp,"%s",information);
		enter(v,name,information,i); 
	}
    printf("\n\n");
    int choice;
	int start;
    do{
    	
        printf("                                                                               \n");
        printf("                                                                               \n");                                 
        printf("                  |-------------0殷墟------1袁林-------2中国文字博物馆         \n");
        printf("                  |              |                  |             |            \n");
        printf("6红旗渠------------              |                  |             |            \n");
        printf("    |             |              |---------------4羑里城-----------            \n");
        printf("    |             |              |                  |             |            \n");
        printf("    |             |              |                  |             |            \n");
        printf("7太行大峡谷-------|-------------3长春观----------5岳飞庙-------   |            \n");
        printf("                                                    |         |   |            \n");
        printf("                                                    |          8二帝陵         \n");
        printf("                                                    |             |            \n");
        printf("                                                    |             |            \n");
        printf("                                                    |----------9明福寺         \n");
        printf("                                                                               \n");
        printf("                                                                               \n");
        printf("*******************************河南安阳旅游地图********************************\n");
        printf("                                                                               \n");
    	printf("              【1】景点名称及相关信息\n");
    	printf("              【2】深度遍历景点\n");
		printf("              【3】获取最短路径\n");
		printf("               请输入你的选项：\n");
		scanf("%d",&choice);
		printf("\n\n\n");
		if(choice==1){
			print_view(v);
			printf("\n");
		}
		if(choice==2){
			int num;
			printf("请输入作为遍历起点的景点编号：");
			scanf("%d",&num);
			DFS(graph, num, visit, visited);
			printf("\n");
		}
		if(choice==3){
			printf("请输入出发地地点编号：\n");
            scanf("%d", &start);
            dijkstra(graph, start, visited);
            printf("\n");
		}
	}while(choice!=0);
	fclose(fp);
    return 0;
}