赞
踩
描述
一张地图包括n个城市,假设城市间有m条路径(有向图),每条路径的长度已知。给定地图的一个起点城市和终点城市,利用Dijsktra算法求出起点到终点之间的最短路径。
输入
多组数据,每组数据有m+3行。第一行为两个整数n和m,分别代表城市个数n和路径条数m。第二行有n个字符,代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d,代表从城市a到城市b有一条距离为d的路。最后一行为两个字符,代表待求最短路径的城市起点和终点。当n和m都等于0时,输入结束。
输出
每组数据输出两行。第一行为一个整数,为从起点到终点之间最短路的长度。第二行为一串字符串,代表该路径。每两个字符之间用空格隔开。
输入样例
(书中倒数第五行应更改为E D 20)
3 3 A B C A B 1 B C 1 A C 3 A C 6 8 A B C D E F A F 100 A E 30 A C 10 B C 5 C D 50 E D 20 E F 60 D F 10 A F 0 0
输出样例
2
A B C
60
A E D F
C语言代码
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct Node{ /*存储城市信息的结构体*/ int symble; /*类似于dijkstra算法中S集的标志,1为已在S集*/ char name; /*城市名*/ int distance; /*距离起始城市的距离*/ struct Node *next; /*将所有城市结构通过next组成链表*/ struct Node *before; /*当前城市距离起始城市最短路径的上一城市*/ }node,*nodeptr; nodeptr find(nodeptr,char**,int,int*,int); /*找到类似dijkstra算法中的最小值顶点*/ nodeptr get(nodeptr,char); /*根据名字确定并返回对应城市的结构体*/ void Free(nodeptr); /*释放内存*/ main() { int city,road; /*存储城市总数、道路总数*/ for(scanf("%d %d",&city,&road),getchar(); city!=0&&road!=0; scanf("%d %d",&city,&road),getchar(
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。