最短路扩展问题

图论

稀疏图的存储可以使用:
vector 存边 / vector>(不需要存边 )
或者first/next数组，存储边的链表

稠密图直接还是用二维数组来存吧

次短路

Question（1）：给定一个图，求次短路。
对于次短路，很容易想到在比较的时候进行处理。
设dis(u)为原点s到u的最短路径，u为当前节点，v和u有边相连。
x = dis[v] + f[u][v];
则对于最短路：if(dis[u] > x) dis[u] = x;
而对于次短路：
if(dis[u]>x) dis2[u]=dis[u],dis[u]=x;
else if(dis2[u]>x) dis2[u]=x;

所以，对于次短路，只需加多一个数组即可。

第k最短路

http://www.cnblogs.com/acSzz/archive/2012/07/31/2616268.html
http://www.xuebuyuan.com/574281.html

f(n)=g(n)+h(n);h(n)就是我们所说的‘启发式函数’，表示为重点t到其余一点p的路径长度，g（n）表示g当前从s到p所走的路径的长度。
(1)将有向图的所有边反向,以原终点t为源点,求解t到所有点的最短距离;
(2)新建一个优先队列,将源点s加入到队列中;
(3)从优先级队列中弹出f(p)最小的点p,如果点p就是t,则计算t出队的次数;
如果当前为t的第k次出队,则当前路径的长度就是s到t的第k短路的长度,算法结束;
否则遍历与p相连的所有的边,将扩展出的到p的邻接点信息加入到优先级队列;

Leetcode 787

求最短路径，但是最短路径的长度过程中的跳点要求不能超过K个，我们看一下正常的求最短路的模板。

bool done[MAXN];
for (int i =0; i < n; i++) d[i] = (i == 0 ? 0 : INF);
memset(done, 0, sizeof(done));
q.push(make_pair(d[0], 0));
while (!q.empty()) {
    pii u = q.top();q.pop();
    int x = u.second;
    if (done[x]) continue;
    done[x] = true;

    for (int e = first[x]; e != -1; e = next[e]) 
    //这个题目里边可能在达到某个节点的时候出现两种情况:
    1. d小但是k大
    2. d大但是k小
    // 这里的这个d数组只能记录下最优的，不能记录下次优的，如果是下边的写法的话不能保证pq里边有所有的结果情况
    if (d[v[e]] > d[x] + w[e]) {
        d[v[e]] = d[x] + w[e];
        q.push(make_pair(d[v[e]]), v[e]);
    }
}

src和dst都固定的时候，就没必要再用使用一个dst数组了。

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, Map<Integer, Integer>> prices = new HashMap<>();
        for (int[] f : flights) {
            if (!prices.containsKey(f[0])) prices.put(f[0], new HashMap<>());
            prices.get(f[0]).put(f[1], f[2]);
        }
        // 将k也放进去
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> (Integer.compare(a[0], b[0])));
        pq.add(new int[] {0, src, k + 1});
        while (!pq.isEmpty()) {
            int[] top = pq.remove();
            int price = top[0];
            int city = top[1];
            int stops = top[2];
            if (city == dst) return price;
            // k符合要求才进行松弛，否则这个点只能由d更大但是k更小的候选者来进行递归下去
            //换句话来说，pq里边的点都是符合要求的
            if (stops > 0) {
                Map<Integer, Integer> adj = prices.getOrDefault(city, new HashMap<>());
                // 所有的结果(d大d小)都有
                for (int a : adj.keySet()) {
                    pq.add(new int[] {price + adj.get(a), a, stops - 1});
                }
            }
        }
        return -1;
}