有 n 个城市通过一些航班连接。给你一个数组 flights 其中 flightsi = starti endi pricei 表示该航班都从城市 starti 开始以价格 pricei 抵达 endi。现在给定所有的城市和航班以及出发城市 src 和目的地 dst你的任务是找到一条中转的路线使得从 src 到 dst 的 总价格最便宜 并返回该价格。 题目保证了这样的路线一定存在。impor

本题可以使用 Dijkstra 算法来求解。Dijkstra 算法是一种贪心算法，每次选择当前距离起点最近的节点作为中转点更新其它节点的距离。具体实现可以使用优先队列来维护距离起点的距离。

首先将所有航班信息存储在邻接表中，然后从起点开始使用 Dijkstra 算法求解最短路径。在 Dijkstra 算法的过程中需要维护每个节点到起点的距离，以及已经确定最短路径的节点集合。每次从距离起点最近的未确定最短路径的节点中选择一个作为中转点，更新其它节点的距离。在更新距离时需要注意，如果当前节点到中转点的距离加上中转点到目标节点的距离小于目标节点的当前距离，那么需要更新目标节点的距离。

最后返回终点的距离即可。如果终点的距离为无穷大，则说明无法到达终点。

具体实现见下：

import java.util.*;

/**

• 航班类Flight的定义，你可在代码中直接使用
• public class Flight {

• int getId(); // 唯一标识符（除了唯一以外并无实质意义）
  

• String getStart();  // 起点名称，名称相同表示同一地点
  

• String getEnd();    // 终点名称，名称相同表示同一地点
  

• int getPrice();     // 从起点飞往终点的机票价格
  

• } */

public class CheapestPriceSolution {

/**
 * 计算最便宜的机票总价钱
 * @param n 表示最多总共有n个城市
 * @param flights 所有航班信息，以对象数组给出，每个Flight对象表示一个航班数据（起点-终点-价格）
 * @param src 起点的名称
 * @param dst 终点的名称
 * @return 搜索一条路径可以从起点转乘一直飞到终点，并且机票总价格最小，输出最小机票价格
 */
public int findCheapestPrice(int n, Flight[] flights, String src, String dst) {
    // 将航班信息存储在邻接表中
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (Flight flight : flights) {
        int start = getCityId(flight.getStart());
        int end = getCityId(flight.getEnd());
        int price = flight.getPrice();
        graph.get(start).add(new int[]{end, price});
    }
    
    // 初始化距离和已确定最短路径的节点集合
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[getCityId(src)] = 0;
    Set<Integer> visited = new HashSet<>();
    
    // 使用优先队列维护距离起点的距离
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{getCityId(src), 0});
    
    // 使用 Dijkstra 算法求解最短路径
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int currId = curr[0];
        if (visited.contains(currId)) {
            continue;
        }
        visited.add(currId);
        if (getCityName(currId).equals(dst)) {
            return dist[currId];
        }
        for (int[] next : graph.get(currId)) {
            int nextId = next[0];
            int price = next[1];
            if (!visited.contains(nextId) && dist[currId] != Integer.MAX_VALUE
                    && dist[currId] + price < dist[nextId]) {
                dist[nextId] = dist[currId] + price;
                pq.offer(new int[]{nextId, dist[nextId]});
            }
        }
    }
    
    // 无法到达终点
    return -1;
}

// 将城市名称映射为编号
private Map<String, Integer> cityIdMap = new HashMap<>();
private int cityId = 0;
private int getCityId(String name) {
    if (!cityIdMap.containsKey(name)) {
        cityIdMap.put(name, cityId++);
    }
    return cityIdMap.get(name);
}
private String getCityName(int id) {
    for (Map.Entry<String, Integer> entry : cityIdMap.entrySet()) {
        if (entry.getValue() == id) {
            return entry.getKey();
        }
    }
    return null;
}