题目描述

求最短路和次短路的条数

算法

(最短路) $O(T * mlog(n))$

1. 设状态$dist[i][0,1]$表示初始城市$S$到城市$i$的最短距离和次短距离，$cnt[i][0,1]$表示城市$S$到城市$i$的最短路径和次短路经的条数
2. 初始时，$dist[S][0]$为0，$cnt[S][0]$为1（其余都初始化成正无穷，初始时S不存在次短路）
3. Dijkstra算法枚举城市$t$可通往的城市$j$时，有四种情况：
   • $dist[j][0] > dist[v][type] + w[i]$：当前最短路变成次短路，更新最短路，将最短路和次短路加入优先队列
   • $dist[j][0] = dist[v][type] + w[i]$：找到一条新的最短路，更新最短路条数
   • $dist[j][1] > dist[v][type] + w[i]$：找到一条更短的次短路，覆盖掉当前次短路，加入优先队列
   • $dist[j][1] = dist[v][type] + w[i]$：找到一条新的次短路，更新次短路条数
4. 到F城市的次短路径如果比最短路径恰好多1，则把这样的路径条数加到答案里
5. C++优先队列大根堆需要重载小于号，小根堆需要重载大于号

时间复杂度

• T组数据，每组需要做一次堆优化的Dijkstra算法，故总时间复杂度为$O(T * mlog(n))$。

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1010, M = 100010;

int cases, n, m, S, F;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2], cnt[N][2];
bool st[N][2];

struct Node {
    int id, type, dist;

    bool operator> (const Node& node) const {
        return dist > node.dist;
    }
};

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra() {
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[S][0] = 0, cnt[S][0] = 1;

    priority_queue<Node, vector<Node>, greater<Node>> q;
    q.push({S, 0, 0});

    while (q.size()) {
        auto t = q.top(); q.pop();

        int v = t.id, type = t.type;
        if (st[v][type]) continue;
        st[v][type] = true;

        for (int i = h[v]; ~i; i = ne[i]) {
            int j = e[i];

            if (dist[j][0] > dist[v][type] + w[i]) {
                dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0];
                q.push({j, 1, dist[j][1]});
                dist[j][0] = dist[v][type] + w[i], cnt[j][0] = cnt[v][type];
                q.push({j, 0, dist[j][0]});
            }
            else if (dist[j][0] == dist[v][type] + w[i]) cnt[j][0] += cnt[v][type];
            else if (dist[j][1] > dist[v][type] + w[i]) {
                dist[j][1] = dist[v][type] + w[i], cnt[j][1] = cnt[v][type];
                q.push({j, 1, dist[j][1]});
            }
            else if (dist[j][1] == dist[v][type] + w[i]) cnt[j][1] += cnt[v][type];
        }
    }

    int ret = cnt[F][0];
    if (dist[F][0] + 1 == dist[F][1]) ret += cnt[F][1];

    return ret;
}

int main() {
    cin >> cases;

    while (cases -- ) {
        cin >> n >> m;

        memset(h, -1, sizeof h);
        idx = 0;
        while (m -- ) {
            int a, b, c; cin >> a >> b >> c;
            add(a, b, c);
        }

        cin >> S >> F;

        cout << dijkstra() << endl;
    }

    return 0;
}