最短路问题（三）

最短路计数问题

树形 dp 统计条数

Sightseeing

不妨设起点为 $s$，终点为 $t$，首先用 $\text{dijkstra}(s)$ 求出单源最短路
得到 $\forall \ u \in V: \ d(u)$

先不考虑 “比最短路长度多 $1$” 这种情况，$f(v)$ 表示 $s \to v$ 最短路可选方案数
对于边 $(u, v)$，显然有转移
$\textbf{if} \ d(v) = d(u) + e(u, v): \ f(v) += f(u)$
初始化 $f(s) = 1, \ \forall u \neq s: \ f(u) = 0$

如果顺着某条路径从 $s$ 到达 $v$，路线长度恰好比最短路多 $1$，那么有
$s \to u$ 沿最短路走，接着 $d(u) + e(u, v) = d(v) + 1$，然后 $v \to t$ 继续沿着最短路走
对于节点 $u$，考虑 $\forall v, e(u, v)$，如果 $d(u) + e(u, v) = d(v) + 1$
则 $f(u)$ 对 $v$ 在 “$s \to v$ 长度恰好比最短路多 $1$” 的答案有贡献

不妨用 $f(0, u)$ 表示 $u$ 在 $s \to u$ 最短路径上的方案数
$f(1, u)$ 表示 $s \to u$ 的距离恰好为最短路径多 $1$ 的方案数，边 $(u, v)$ 存在转移

• 如果 $d(v) = d(u) + e(u, v)$，那么 $f(0, v) += f(0, u), \ f(1, v) += f(1, u)$
• 如果 $d(v) + 1 = d(u) + e(u, v)$，那么 $f(1, v) += f(0, u)$

初始化 $\forall u: f(0,u) = f(1, u) = 0, \quad f(0, s) = 1$
最后答案为 $f(0, t) + f(1, t)$

具体来说
先 $\text{dijkstra}(s)$ 求出单源最短路 $\forall u: d[u]$，接下来对所有节点 $u$
根据 $d[u]$ 从小到大排序，对于每个节点 $u$，执行如上 $\text{dp}$

容易弄错的地方是，由于存在 $f(0, u) \to f(1, v)$ 的转移
所以 $\text{dp}$ 枚举节点的时候，需要把 $\forall u, f(0, u)$ 先算出来，再算 $f(1, u)$

最短路组合计数

社交网络
$C_{s, t}(v)$ 表示经过 $v$ 的从 $s \to t$ 的最短路数目，可以考虑用 floyd 算法求解

先执行 floyd 算法，求出任意两点之间的最短路径 $\forall u, v: f(u, v)$
下面来考虑任意两点间最短路数目 $C(u, v)$ 如何求解，先将任意两点的 $C(u, v)$ 初始化为 $1$
对于 floyd 方程中满足 $f(u, v) = f(u, k) + f(k, v)$，令 $C(u, v) += C(u, k) \cdot C(k, v)$
如果 $f(u, v) > f(u, k) + f(k, v)$，则令 $C(u, v) \leftarrow C(u, k) \cdot C(k, v)$

$C_{s, t}(k)$ 求解就比较简单，当发现满足 $f(s, t) = f(s, k) + f(k, t)$ 时，对于点 $k$
可以直接统计，$\displaystyle I(k) += \frac{C_{s, t}(k)}{C(s, t)}$，实际上
$C_{s, t}(k) = C(s, k) \cdot C(k, t)$

建新图统计

有时候图论的统计问题，预处理执行完最短路算法后，可以根据 $d(u)$ 信息
重新建图，新图往往是一个 $\text{DAG}$，可以执行 $\text{DAG}$ 上的 $\text{dp}$

林中漫步

很容易想到满足从公司到家的路径，一定是一条最短路，问题就是最短路可能不止一条，执行单源最短路算法后
可以得到任意节点的距离信息 $\forall u, \ d(u)$
满足条件的道路 $A \to B$，实际上要求 $d(B) < d(A)$，可以设计出如下算法

原图起点 $s$，终点 $t$，先反着执行 $\text{dijkstra}(t)$，得到 $d(u)$
从 $t \to s$ 反着来执行 $\text{DAG}$ 上的 $\text{dp}$，不妨用 $f(u)$ 表示从 $u$ 出发的路径方案
边界为 $f(s) = 1$

具体来说，枚举每一条边 $e(u, v)$，建立新图，当且仅当 $d(u) > d(v)$ 时加入有向边 $(u, v)$
然后执行 $dp(t)$，统计的时候，$\textbf{for} \ \forall v \in son(u): \ f(u) += dp(v)$
$dp(t)$ 就是答案

typedef pair<int, int> PII;

const int maxn = 1000 + 10, inf = 0x3f3f3f3f;
const int maxm = 200000 + 10;
int n, m;
vector<PII> edges(maxm, PII(0, 0));

namespace Graph {
    int n1 = 1, n2 = 1;
    int h1[maxn], ver1[maxm], e1[maxm], ne1[maxm];
    int h2[maxn], ver2[maxm], e2[maxm], ne2[maxm];

    void initG() {
        n1 = n2 = 1;
        memset(h1, 0, sizeof h1);
        memset(h2, 0, sizeof h2);
        fill(edges.begin(), edges.end(), PII(0, 0));
    }

    void add1(int a, int b, int c) {
        ver1[++n1] = b, e1[n1] = c, ne1[n1] = h1[a], h1[a] = n1;
        edges[n1] = PII(a, b);
    }
    void add2(int a, int b, int c) {
        ver2[++n2] = b, e2[n2] = c, ne2[n2] = h2[a], h2[a] = n2;
    }
}

vector<int> d(maxn, inf);
int vis[maxn];

void dijkstra(int s) {
    using namespace Graph;

    priority_queue<PII, vector<PII>, greater<PII> > q;
    fill(d.begin(), d.end(), inf);
    memset(vis, 0, sizeof vis);
    d[s] = 0, q.push(PII(0, s));

    while (q.size()) {
        auto x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;

        for (int i = h1[x]; i; i = ne1[i]) {
            int y = ver1[i];
            if (d[y] > d[x] + e1[i]) {
                d[y] = d[x] + e1[i];
                q.push(PII(d[y], y));
            }
        }
    }
}

void build() {
    using namespace Graph;
    for (int i = 2; i <= n1; i++) {
        int u = edges[i].first, v = edges[i].second, w = e1[i];
        //debug(d[u]);
        if (d[u] > d[v]) add2(v, u, w);
    }
}

ll f[maxn];
ll dp(int x) {
    using namespace Graph;

    if (f[x]) return f[x];
    for (int i = h2[x]; i; i = ne2[i]) {
        int y = ver2[i];
        //debug(y);
        f[x] += dp(y);
    }
    return f[x];
}

void init() {
    memset(f, 0, sizeof f);
    f[1] = 1;
}

int main() {
    freopen("input.txt", "r", stdin);
    using namespace Graph;

    while (scanf("%d%d", &n, &m) == 2 && n) {
        //init();
        initG();

        // get data
        while (m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add1(a, b, c), add1(b, a, c);
        }

        dijkstra(2);

        // build and dp
        build();

        init();
        ll res = dp(2);
        printf("%lld\n", res);
    }
}

最短路建模

如何把一些问题抽象成最短路来解决，这也是算法中关注的焦点
最短路建模常用的技巧比如拆点，在实际开发过程中非常常用

Dijkstra 模版

机场快线
本例可作为 dijkstra 模板题

本例中起点 $s$，终点 $t$ 都是确定的，很容易想到用单源最短路径解决
由于商业线只可以坐一站，可以枚举在哪一站开始坐商业线，不妨设在 $a$ 站开始换乘商业线
我们需要最小化 $\min$ $f(s, a) + T(a, b) + f(b, t)$ 的值，其中 $T(a, b)$ 表示商业线 $a \to b$ 耗费的时间

很显然 $f(s, a)$ 必然是经济线中 $s \to a$ 的最短路径，$f(b, t)$ 也是 $b \to t$ 的最短路径
由于道路双向的，可以考虑预处理 $\text{dijkstra}$，分别求出对于任意节点 $u$
从 $s$ 出发的单源最短路 $f(u)$，和从 $t$ 出发的最短路 $g(u)$，这样只需要枚举中转站 $a$
求出 $\min f(a) + T(a, b) + g(b)$ 即可

值得注意的是，很可能不需要用到商业线车票，在输出方案的时候
只在 $f(t) > f(a) + T(a, b) + g(b)$ 的时候，更新中转点 $res \leftarrow a$

const int maxn = 1000 + 10, maxm = 2000 + 10;
const int inf = 0x3f3f3f3f;
int n, s, t, m, k, T[maxn][maxn];

namespace Graph {
    int idx = 1;
    int head[maxn], ver[maxm], ne[maxm], e[maxm];

    void initG() {
        idx = 1;
        memset(head, 0, sizeof head);
    }

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

int vis[maxn];
typedef pair<int, int> PII;
void dijkstra(int s, vector<int> &f, vector<int> &p) {
    using namespace Graph;
    fill(p.begin(), p.end(), 0);
    fill(f.begin(), f.end(), inf);
    memset(vis, 0, sizeof vis);

    f[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push(PII(0, s));

    while (q.size()) {
        auto x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;

        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (f[y] > f[x] + e[i]) {
                f[y] = f[x] + e[i], p[y] = x;
                q.push(PII(f[y], y));
            }
        }
    }
}

vector<int> f(maxn, inf), g(maxn, inf), pf(maxn, 0), pg(maxn, 0);
vector<PII> vec;

void dfs(const int u, const vector<int> &p, vector<int> &path) {
    if (u == 0) return;

    dfs(p[u], p, path);
    path.push_back(u);
}

void solve() {
    PII res(-1, -1);
    dijkstra(s, f, pf), dijkstra(t, g, pg);

    int ans = f[t];
    for (auto x : vec) {
        int u = x.first, v = x.second;

        for (int kase = 0; kase < 2; kase++) {
            if (ans > f[u] + T[u][v] + g[v]) {
                ans = f[u] + T[u][v] + g[v];
                res = PII(u, v);
            }
            swap(u, v);
        }
    }

    // get path
    if (res.first == -1) {
        vector<int> path;
        dfs(t, pf, path);
        int fl = 0;
        for (auto x : path) {
            printf("%d", x);
            ++fl == (int)path.size() ? printf("\n") : printf(" ");
        }
    }
    else {
        vector<int> path1, path2;
        int u = res.first, v = res.second;
        dfs(u, pf, path1), dfs(v, pg, path2);
        reverse(path2.begin(), path2.end());

        vector<int> path;
        for (auto x : path1) path.push_back(x);
        for (auto x : path2) path.push_back(x);

        int fl = 0;
        for (auto x : path) {
            printf("%d", x);
            ++fl == path.size() ? printf("\n") : printf(" ");
        }
    }

    if (res.first == -1) puts("Ticket Not Used");
    else printf("%d\n", res.first);
    printf("%d\n", ans);
}

void init() {
    memset(T, 0, sizeof T);
    vec.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    using namespace Graph;

    int cas = 0;
    while (scanf("%d%d%d", &n, &s, &t) == 3) {
        init();
        initG();
        if (cas++ != 0) puts("");

        // build
        scanf("%d", &m);
        while (m--) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z), add(y, x, z);
        }

        scanf("%d", &k);
        while (k--) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            vec.push_back(PII(x, y));
            T[x][y] = T[y][x] = z;
        }

        // dijkstra
        solve();
    }
}

最短路树与删边最短路

Codeforces 1163F Indecisive Taxi Fee

给定一个 $n$ 个点 $m$ 条双向边的无向图 $G$，第 $i$ 条道路通行费用为 $w_i$
经过 $e_1, e_2, \cdots, e_k$ 的总花费为 $\sum_{i = 1}^{k} w_{e_k}$

下面有 $q$ 个问询，每个问询为 $(t_j, x_j)$，把编号为 $t_j$ 的边的权值更改为 $x_j$
对于每个问询，回答从 $1 \to n$ 的最小花费

最短路删边问题，可以考虑用最短路树，先来看最短路树的一个性质

很容易想到先求出原来的最短路树 $L$

• 对于每个问询，如果修改的边 $e_i(u, v)$ 不是最短路树上的边，不妨设旧边权为 $w_i$，修改后的边权为 $x_i$
  对于任意点 $u$，在原图上从 $s$ 开始跑一遍最短路记为 $f(u)$
  再从 $t$ 开始跑一遍最短路记为 $g(u)$
  则修改后的最短路径为 $\min\{f(t), \ f(u) + g(v) + x_i, \ f(v) + g(u) + x_i\}$
• 如果 $e_i(u, v)$ 是最短路树上的边，并且 $x_i < w_i$，修改后的权值比原来权值更小
  最短路仍然是 $L$，求解的结果为 $f(t) - w_i + x_i$

具体到编程实现上，最短路树可以用 $\text{dijkstra}$ 求出 $(p(u), u)$
对于编号为 $i$ 的边，需要知道 $\text{edges}(i) = (u, v)$，并且 $\text{inTree}(u, v)$ 标记这条边是不是树边
这样以上情况都可以解决

下面来讨论 $e_i(u, v)$ 代价增大的情况，当 $x_i > w_i$ 时候，最短路树可能就不是 $L$ 了
可以推出一个结论，新的最短路树 $L'$ 和 $L$ 有着相同的前缀和后缀，可以为空

不妨设 $L$ 中的节点为 $\{s, u_1, u_2, \cdots u_k, t\}$，如果 $L'$ 和 $L$ 没有公共前缀
设 $L'$ 路径为 $s \to [p_1, p_2, \cdots p_k] \to [u_{l}, u_{l+1}, \cdots]$
而在 $\text{dijkstra}$ 中求出 $f(u_l)$，从 $s \to u_{l}$ 的最短路径为
$s \to u_1 \to u_2 \to \cdots \to u_l$，这条路径一定不会比其他路径更差，这与假设矛盾

根据这个结论，我们需要快速计算出不经过 $L[l, r]$ 的最短路，称为非树边最短路
实际上在 $\text{dijkstra}$ 的时候，对于每一条非树边 $(u, v)$，需要快速求出 $\text{le}(u), \text{ri}(v)$
即 $u$ 往左能够连到最短路树上 $\text{le}(u)$ 的点，$\text{ri}(v)$ 同理
那么非树边最短路不经过原最短路树 $[\text{le}(u), \text{ri}(v)-1]$ 这一段（左开右闭）
此时非树边最短路径为 $z = f(u) + w(u, v) + g(v)$
这个值对不经过原最短路树上 $[\text{le}(u), \text{ri}](v)-1]$ 这一段，所形成的最短路径有贡献

这启发我们用线段树维护 $\text{minv}$，即不经过最短路上 $[li, ri]$ 区间，所形成的最短路径
首先将最短路树上的点离散化，$u \to \text{ID}(u)$
对每一个非树边 $(u, v)$，执行区间修改 $\text{change}(\text{le}(u), \text{ri}(v)-1, z)$
这样处理问询 $e(u, v)$ 的时候，就是线段树的标准查询，$\text{query}(\text{ID}(u))$ 即可
实际上我们要问询不经过 $e(u, v)$ 的最短路，由于左开右闭建线段树，所以问询不经过 $\text{ID}(u)$ 的最短路

最后就是编程实现，如何快速求出 $\text{le}(u), \text{ri}(v)$
由于非树边最短路 $L'$ 和 $L$ 有公共前缀，先 $\text{dijkstra}$ 求出最短路树，并标记点是否在树上
对于最短路树上的点 $u$，显然 $\text{le}(u) = \text{ri}(u) = \text{ID}(u)$
再从 $s$ 开始再执行 $\text{dijkstra}$，执行松弛 $f(y) \leftarrow \min(f(x) + w(x, y))$ 的时候
如果 $y$ 不在最短路树上，那么 $y$ 可以连接到 $x$，执行 $\text{le}(y) \leftarrow le(x)$
对称地从 $t$ 开始再来一次 $\text{dijkstra}$ 求出 $ri(u)$

typedef pair<int, int> PII;
typedef pair<ll, int> PLL;
const int maxn = 4e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, q;

namespace Graph {
    int idx = 1;
    int ver[maxn], e[maxn], ne[maxn], id[maxn], h[maxn];
    
    void initG() {
        idx = 1;
        memset(h, 0, sizeof h);
    }

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

namespace segTree {
    struct node {
        bool fl;
        ll minv;
        node() {
            fl = 0, minv = inf;
        }
    };
    vector<node> t(maxn<<2, node());

    inline void push(int p) {
        if (t[p].fl) {
            t[p].fl = 0, t[p<<1].fl = 1, t[p<<1|1].fl = 1;
            chmin(t[p<<1].minv, t[p].minv);
            chmin(t[p<<1|1].minv, t[p].minv);
        }
    }

    void change(int p, int l, int r, const int li, const int ri, ll val) {
        if (li <= l && r <= ri) {
            t[p].fl = 1, chmin(t[p].minv, val);
            return;
        }

        push(p);
        int mid = (l + r) >> 1;
        if (li <= mid) change(p<<1, l, mid, li, ri, val);
        if (ri > mid) change(p<<1|1, mid+1, r, li, ri, val);
        //pull(p);
    }

    ll query(int p, int l, int r, int cur) {
        if (l == r) {
            return t[p].minv;
        }
        push(p);
        int mid = (l + r) >> 1;
        if (cur <= mid) return query(p<<1, l, mid, cur);
        else return query(p<<1|1, mid+1, r, cur);
    }
}

using namespace Graph;
using namespace segTree;
PII edges[maxn];
int w[maxn];

vector<ll> f[2];
vector<PII> p[2];
int vis[maxn];

vector<int> line;
int onPath[maxn], inTree[maxn];

int cnt = 0;
vector<int> le(maxn, 0), ri(maxn, 0);
map<int, int> mp;

void build() {
    cnt = 0, mp.clear();
    for (auto x : line) mp[x] = ++cnt;
    for (auto x : line) le[x] = ri[x] = mp[x];
}

void dijkstra(int s, vector<ll> &f, vector<PII> &p, int fl = 0) {
    priority_queue<PLL, vector<PLL>, greater<PLL> > q;
    fill(f.begin(), f.end(), inf), fill(p.begin(), p.end(), PII(0, 0));
    memset(vis, 0, sizeof vis);

    f[s] = 0;
    q.push(PLL(f[s], s));

    while (q.size()) {
        auto x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;

        for (int i = h[x]; i; i = ne[i]) {
            int y = ver[i];
            if (f[y] > f[x] + e[i]) {
                f[y] = f[x] + e[i], p[y] = PII(x, id[i]);

                if (fl == 1 && !onPath[y]) le[y] = le[x];
                else if (fl == 2 && !onPath[y]) ri[y] = ri[x];
                q.push(PLL(f[y], y));
            }
        }
    }
}

void get_path(int u, const vector<PII> &p, vector<int> &path) {
    if (!u) return;
    get_path(p[u].first, p, path);
    path.push_back(u);
    if (p[u].second) inTree[p[u].second] = 1;
}


void prework() {
    dijkstra(1, f[0], p[0]);
    get_path(n, p[0], line);

    for (int i = 0; i < line.size()-1; i++) {
        int u = line[i], v = line[i+1];
        onPath[u] = onPath[v] = 1;
    } 
}

void upd() {
    for (int i = 1; i <= m; i++) {
        if (inTree[i]) continue;
        int u = edges[i].first, v = edges[i].second;
        ll z = f[0][u] + w[i] + f[1][v];
        //debug(z);
        if (le[u] <= ri[v]-1) change(1, 1, cnt-1, le[u], ri[v]-1, z);

        swap(u, v);
        z = f[0][u] + w[i] + f[1][v];
        if (le[u] <= ri[v]-1) change(1, 1, cnt-1, le[u], ri[v]-1, z);
    }
}

void init() {
    for (int i = 0; i < 2; i++) {
        f[i].resize(maxn), p[i].resize(maxn);
        fill(f[i].begin(), f[i].end(), inf), fill(p[i].begin(), p[i].end(), PII(0, 0));
    }

    line.clear();
    memset(onPath, 0, sizeof onPath);
    memset(inTree, 0, sizeof inTree);
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m >> q;
    initG(), init();

    // graph
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c, i), add(b, a, c, i);
        edges[i] = PII(a, b), w[i] = c;
    }

    prework(), build();
    dijkstra(1, f[0], p[0], 1), dijkstra(n, f[1], p[1], 2);

    upd();

    // query
    while (q--) {
        int id, x;
        scanf("%d%d", &id, &x);

        if (!inTree[id]) {
            ll res = f[0][n];
            int u = edges[id].first, v = edges[id].second;
            chmin(res, f[0][u] + x + f[1][v]);
            chmin(res, f[1][u] + x + f[0][v]);
            printf("%lld\n", res);
        }
        else {
            int u = edges[id].first, v = edges[id].second;
            if (w[id] > x) {
                ll res = f[0][u] + x + f[1][v];
                chmin(res, f[0][v] + x + f[1][u]);
                printf("%lld\n", res);
                continue;
            }
            ll res = f[0][n] - w[id] + x;
            chmin(res, f[0][u] + x + f[1][v]);
            chmin(res, f[1][u] + x + f[0][v]);
            //debug(res);
            int cur = min(mp[u], mp[v]);

            chmin(res, query(1, 1, cnt-1, cur));
            printf("%lld\n", res);
        }
    }
}