PAT 甲级题解 - 1111 Online Map

发表于 分类于 ， Waline： 阅读次数： 本文字数： 350 阅读时长 ≈ 1 分钟
题目大意

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

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

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

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

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