算法提高课汇总

理解题意

本题在 AcWing 1134. 最短路计数 计算最短路路径数的基础上要求我们额外计算路径长度恰好
比最短路多$1$的路径数. 如果这样的路径存在, 那么该路径一定是次短路. 我们可以计算从起点
到终点的次短路路径数, 并判断次短路路径长度是否满足恰好比最短路多$1$, 若满足则加上次短路
路径数即可.

模型抽象

考虑用 AcWing 1131. 拯救大兵瑞恩 拆点的思路将顶点的状态分为两部分:

• $dist[v][0]$: 从起点到$v$的最短路的长度.

• $dist[v][1]$: 从起点到$v$的次短路长度.

我们通过上题知道用某些最短路算法(如$djkstra$)计算最短路是按拓扑序得到顶点的最短路长度的.

图算法具有拓扑序的含义并不是图或者最短路图是拓扑图(有向无环)的: $djkstra$算法可以计算非
拓扑图的最短路径; 通过$spfa$算法得到的最短路图也是拓扑图. 图算法具有拓扑序的含义是得到
某个顶点的最短路径值(全局最小值)的顺序是沿着最短路拓扑图的(按拓扑顺序得到), 在用$u$更新
其他顶点时, 可以保证其全局最小值已经得到. (站在算法过程的角度: 每个顶点只会出队1次).

那么在计算次短路的过程中, 用$dijkstra$是否仍然满足拓扑序呢? 或者我们是否可以说, 当我们用顶点$u$
的次短路径更新其他顶点的状态时(当$u$次短路径状态出队时), 能否保证其全局次短路径已经确定?

• 用最短和次短将顶点拆分为两个状态, 同时在算法中进行计算即可保证次短路的状态也具有拓扑序.

代码实现 $djkstra$

顶点最短和次短两个状态同时计算, 计算更新的过程类似于在一个数组中找第二小的值.

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, M = 10010;

struct Ver
{
    int v, type, dis; //type = 0: 最短路; type = 1: 次短路
    bool operator> (const Ver &V) const
    {
        return dis > V.dis;
    }
};

int n, m, s, t;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2]; bool st[N][2]; //dijkstra
int cnt[N][2]; //cnt[u][0]/cnt[u][1]: 从起点到u的最短路/次短路的路径数

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

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

    priority_queue<Ver, vector<Ver>, greater<Ver>> heap;
    heap.push({s, 0, dist[s][0]}); //(v, type, dis)

    while( heap.size() )
    {
        Ver cur = heap.top(); heap.pop();
        int v = cur.v, dis = cur.dis, type = cur.type, count = cnt[v][type];

        if( st[v][type] )   continue;
        else    st[v][type] = true;

        for( int i = h[v]; ~i; i = ne[i] )
        {
            int u = e[i];
            if( dist[u][0] > dis + w[i] )
            {//更新最优
                dist[u][1] = dist[u][0]; cnt[u][1] = cnt[u][0];
                dist[u][0] = dis + w[i]; cnt[u][0] = count;

                heap.push({u, 0, dist[u][0]});
                heap.push({u, 1, dist[u][1]});
            }
            else if( dist[u][0] == dis + w[i] )
            {
                cnt[u][0] += count; //累加路径数
            }
            else if( dist[u][1] > dis + w[i] )
            {//更新次优
                dist[u][1] = dis + w[i];
                cnt[u][1] = count;
                heap.push({u, 1, dist[u][1]});
            }
            else if( dist[u][1] == dis + w[i] )
            {
                cnt[u][1] += count;
            }
        }
    }

    int res = cnt[t][0];
    if( dist[t][0] + 1 == dist[t][1] )
    {//满足次短路等于最短路+1
        res += cnt[t][1];
    }
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    while( T -- )
    {
        scanf("%d%d", &n, &m);

        memset(h, -1, sizeof h);
        idx = 0;
        while( m -- )
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d%d", &s, &t);

        printf("%d\n", dijkstra());
    }
    return 0;
}