0%

PAT甲级题解-1111 Online Map

题目大意

  给定一有向图,以及起点与终点,求最短路径及最快路径。求路径时,涉及2个比较条件;输出时,要根据情况分类输出。

练题地址:拼题A
代码地址:Github

涉及算法
  • Dijkstra最短路径
解题思路

  典型的最短路径问题,但本题不同之处在于需要调用两次Dijkstra算法,求出一条最短路径及一条最快路径。网上大部分题解都重复编写两次Dijkstra算法,这里给出一种复用代码的新思路,利用函数指针,分别创建一个比较最短路径的方法compare_distance,一个比较最快路径的方法compare_time,调用2次Dijkstra算法,分别传入两个比较函数,最后比较两次返回的结果是否一致,并按题目要求输出。

注意点
  • 求最短路径且不唯一时,找出其中最快的路径
  • 求最快路径且不唯一时,找出其中交叉路口最少的路径