最短路

dijkstra

單源點最短路徑

考慮不帶權的單點源最短路，我們用BFS維護一個 queue，每次處理一個點時最短路徑大小已知，因此只需要拿該點去更新其他點一次在沒有負邊的假設下，dijkstra 就像是有帶權的BFS。

模板 CSES - Shortest Routes I

給一張帶正權無向圖,求從節點 $1$ 到其他所有節點的最短路徑。

$1\le n\le {10}^5,1\le m\le 2\times {10}^5$

一旦被選中去 relax 其他人時，就代表 u 這個點已經固定

算法實作1（稍慢）

vector<int> dijkstra(int start) {
    vector<int> dis(n + 1, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    while (pq.size()) {
        auto [dis_u, u] = pq.top();
        pq.pop();
        if (dis[u] != INF) continue;
        dis[u] = dis_u;
        for (auto [v, w] : G[u]) {
            pq.push({w + dis[u], v});
        }
    }
    return dis;
}

算法實作2（稍快）

vector<int> dijkstra(int start) {
    vector<int> dis(n + 1, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    dis[start] = 0;
    while (pq.size()) {
        auto [dis_u, u] = pq.top();
        pq.pop();
        if (dis[u] < dis_u) continue; // 相當於 if (visited)
        dis[u] = dis_u;
        for (auto [v, w] : G[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push ({dis[v], v});
            } 
        }
    }
    return dis;
}

補充 : O(n) 做 dijkstra

當圖邊權範圍上界在 $\approx {10}^5$ 的時候，且權值具有單調性，可使用這個技巧

實作一個 data structure，滿足以下功能 :

• push(x)

• get_value() 得到當前最小的 distance (相當於 pq.top())

因為 distance 具有單調性，故 threshold 只會遞增。類似的技巧也應用在 TIOJ 1915, 2023 一模 pD

為何 dijkstra 不能在有負邊的圖上跑 ?

簡單來說就是因為單調性。

舉例來說，現在要算出 A 到 D 的最短路徑，Dijkstra 首先 relax B, C，B 最短，然後把 B 的出邊進行鬆弛，B 被標記為處理過，然後再次選出 C，對 C 的出邊進行 relax，此時 B 雖然進行了鬆弛，但是前面已經被標記處理過了，所以最後算出來的最短路徑為 35，但是實際上最短路徑為 33。

因為 Dijkstra 是這樣假設的：對於處理過的結點，沒有前往該結點的更短路徑，這種假設僅僅在沒有負權邊時才能成立。

練習

來回 zerojudge g733. 110北二4.漫遊高譚市

給 $n$ 點 $m$ 邊有向圖，邊帶權，另外額外有 $k$ 條無向帶權邊，至多只能走一條這種邊。問 $s\to t$ 的最短路

$n\le {10}^4,m+k\le {10}^5$

思路

對於每個點 $u$ 找 $dis(s\to u)+dis(u\to v)$。正反各做一次，也就是把正圖跟反圖都各做一次 dijkstra。

2021 南一中校內複賽 pC 為美好的地牢獻上爆擊

給一個 $n\times m$ 的棋盤，在某一個格子有一個 ADD 道具，其他每個格子都有一隻魔物攻擊力是 $w_{i,j}$。你要從左上角走到右下角，如果經過的格子有魔物，那你會受到 $w_{i,j}$ 點的傷害，並把那隻魔物打倒，第二次經過這個格子就不會再遇到魔物了。在經過 ADD 道具之後，每次你受到的傷害都會減少(但不會回血)，求你最少要承受多少傷害

$n,m\le {10}^3$

思路

可分為不吃 ADD 與吃 ADD

吃 ADD 的話 起點 → ADD → 終點 做兩張圖 dijkstra 即可

n 平方

給定 $n$ 個點，第 $i$ 點在 $(x_i,y_i)$，從 $i\to j$ 花費 $(x_i-x_j{)}^2+(y_i-y_j{)}^2$。問從 $s\to t$ 的最小花費

字典序 TIOJ 1572.最短路線問題(Path)

給一張 $n$ 點 $m$ 邊無向圖，邊權皆為 $1$，輸出 $s\to t$ 的字典序最小的最短路徑

$n,m\le {10}^6$

思路

從終點做回來，建立最短路徑 DAG，將 DAG 的邊反向，從起點每次 greedy 走最小的點直到抵達終點

最短平均路 CF EDU B. Minimum Average Path

給定一個 $n$ 點 $m$ 邊的 DAG，邊帶權，問從 $1\to n$ 的 path 上權重的平均最小可以是多少

$n\le {10}^5,m\le {10}^5$

思路

跟上面最大平均區間一樣，我們去二分搜平均值 $x$，將邊權都 $-x$，看有沒有一條 path 的總和 $\le 0$。我們可以令 $dp[i]=$ 走到點 $i$ 的最小權值是多少，$dp[v]=min\{dp[u]+w\}$

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const double INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

int n, m;
double dp[maxn];
int par[maxn];
vector<pii> G[maxn];

bool check(double x) {
    fill(dp, dp + n + 1, INF);
    fill(par, par + n + 1, -1);
    dp[1] = 0;
    for (int i = 1; i <= n; i++) {
        for (auto [v, w] : G[i]) {
            double val = (double)dp[i] + w - x;
            if (dp[v] > val) {
                dp[v] = val;
                par[v] = i;
            }
        }
    }
    return dp[n] <= 0;
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].pb({v, w});
    }

    double l = 0, r = 105;
    for (int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    check(l);

    stack<int> stk;
    int x = n;
    stk.push(x);
    while (par[x] != -1) {
        x = par[x];
        stk.push(x);
    }
    cout << stk.size() - 1 << '\n';
    while (stk.size()) {
        cout << stk.top() << ' ';
        stk.pop();
    }
} 

多源點 dijkstra

zerojudge b904. 10. 學園生活

給一張 $n$ 點 $m$ 邊的無向圖，與 $k$ 個源點，求這些點兩兩之間的距離最小值

$n,k,m\le 3\times {10}^5$

思路

最暴力的想法就是枚舉源點，每次都重跑 dijkstra，複雜度 $O(kE\log E)$

從上面暴力的方法我們可以觀察出，要交會的點或邊一定要是源點們之間的最短路。

每個源點能擴展出他能控制的最短路徑區域，如下圖

每個源點擴出自己的範圍

範圍重疊的地方代表他們同時是多個源點的最短路徑，這個就是我們可以取的答案，我們可以用一個數字 $x$ 來控制每個範圍最多能擴張多少權重，一旦目前的 $x$ 能使某些個範圍重疊的這個 $x$ 就可以是答案，我們二分搜 $x$ 找到最小的 $x$ 使得範圍有重疊

二分搜的複雜度為 $O(\log C)$ 其中 $C$ 是值域範圍，每次都需要重新擴張源點的範圍(因為擴張的權重上限被更新了)，為 $O(E\log E)$ 所以複雜度 $O(E\log E\log C)$

但我們真的有需要每次都重新算嗎?

這邊提一個結構叫 shortest path tree 又稱最短路徑樹，每個點 $v$ 都跟自己的最短路徑的上一個點 $u$ 連接，形成一顆樹

我們可以建立最短路徑樹，我們就只需要在樹上 BFS 即可應付每次 $x$ 改變之後的擴張範圍。複雜度 $O(E\log E)$ 建樹，$O(V+E)$ BFS 二分搜 $O(\log C)$，總共 $O(E\log E+(V+E)\log C)$

但其實到頭來我們只是要看重疊的部分，我們也就同樣的建立最短路徑樹，枚舉 edge 使得 $(u,v)$ 是來自不同的源點，$ans$ 去跟他取 min 即可，複雜度 $O(E\log E+E)=O(E\log E)$

枚舉重疊邊

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;
const double EPS = 1e-8;

struct Graph {
    vector<vector<pii>> G;
    vector<int> source;
    vector<int> dis;
    vector<int> par;
    int n;

    void init(int _n) {
        n = _n;
        G.resize(n);
    }

    void add_edge(int u, int v, int w) {
        G[u].pb({v, w});
    }

    void add_source(int x) {
        source.pb(x);
    }

    void dijkstra() {
        dis = vector<int>(n, INF);
        par = vector<int>(n);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        for (auto s : source) {
            pq.push({0, s});
            dis[s] = 0;
            par[s] = s;
        }

        while (pq.size()) {
            auto [dis_u, u] = pq.top();
            pq.pop();

            if (dis_u > dis[u]) continue;
            dis[u] = dis_u;

            for (auto [v, w] : G[u]) {
                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    par[v] = par[u];
                    pq.push({dis[v], v});
                }
            }
        }
    }

    bool check(int D) {
        for (int i = 0; i < n; i++) {
            for (auto [v, w] : G[i]) {
                if (par[i] == par[v]) continue;
                int x = D - dis[i] - dis[v] - w;
                if (x >= 0) {
                    return true;
                }
            }
        }
        return false;
    }
} g;

int n, m, k;

void init() {
    cin >> n >> m >> k;
    g.init(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        g.add_edge(u, v, w);
        g.add_edge(v, u, w);
    }
    for (int i = 0; i < k; i++) {
        int u;
        cin >> u;
        u--;
        g.add_source(u);
    }
}

void work() {
    g.dijkstra();
    int l = 0, r = INF;
    while (l < r) {
        int mid = (l + r) / 2;
        if (g.check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << "\n";
}

signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        init();
        work();
    }
}

---

另解

對於每個非源點的點都去維護他與最近的兩個「不同的」源點的距離

令 $f[u]$ 為 $u$ 的與她最近源點的距離，$g[u]$ 為次近源點的距離，那麼答案就是 $ans=min(ans,f[u]+g[u])$

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;
const double EPS = 1e-8;

struct Graph {
    vector<vector<pii>> G;
    vector<int> source;
    vector<int> f;
    vector<int> parf;
    vector<int> g;
    vector<int> parg;
    int n;

    void init(int _n) {
        n = _n;
        G.resize(n);
    }

    void add_edge(int u, int v, int w) {
        G[u].pb({v, w});
    }

    void add_source(int x) {
        source.pb(x);
    }

    void dijkstra() {
        f = vector<int>(n, INF);
        parf = vector<int>(n);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        for (auto s : source) {
            pq.push({0, s});
            f[s] = 0;
            parf[s] = s;
        }

        while (pq.size()) {
            auto [dis_u, u] = pq.top();
            pq.pop();

            if (dis_u > f[u]) continue;
            f[u] = dis_u;

            for (auto [v, w] : G[u]) {
                if (f[u] + w < f[v]) {
                    f[v] = f[u] + w;
                    parf[v] = parf[u];
                    pq.push({f[v], v});
                }
            }
        }
    }

    int dijkstra2() {
        g = vector<int>(n, INF);
        parg = vector<int>(n, -1);
        priority_queue<pii, vector<pii>, greater<pii>> pq;

        for (int i = 0; i < n; i++) {
            for (auto [v, w] : G[i]) {
                if (parf[i] == parf[v]) continue;
                if (f[i] + w < g[v]) {
                    g[v] = f[i] + w;
                    parg[v] = parf[i];
                    pq.push({g[v], v});
                }
            }
        }

        while (pq.size()) {
            auto [dis_u, u] = pq.top();
            pq.pop();

            if (dis_u > g[u]) continue;
            g[u] = dis_u;

            for (auto [v, w] : G[u]) {
                if (parg[u] == parf[v]) continue;
                if (g[u] + w < g[v]) {
                    g[v] = g[u] + w;
                    parg[v] = parg[u];
                    pq.push({g[v], v});
                }
            }
        }

        int ans = INF;
        for (int i = 0; i < n; i++) {
            if (parg[i] == -1) continue;
            if (parf[i] == parg[i]) continue;
            ans = min(ans, f[i] + g[i]);
        }

        return ans;
    }
} g;

int n, m, k;

void init() {
    cin >> n >> m >> k;
    g.init(n);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        g.add_edge(u, v, w);
        g.add_edge(v, u, w);
    }

    for (int i = 0; i < k; i++) {
        int u;
        cin >> u;
        u--;
        g.add_source(u);
    }
}

void work() {
    g.dijkstra();
    cout << g.dijkstra2() << "\n";
}

signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        init();
        work();
    }
}

shortest path tree

shortest path tree 結構

實作

void build_Tree () {
    fill (par + 1, par + 1 + n, -1);
    for (int i = 1; i <= n; i++) {
        for (auto [v, w] : G[u]) {
            if (dis[v] == dis[u] + w) {
                par[v] = u;
            }
        }
    }
    for (int i = 1; i < n; i++) {
        if (par[i] != -1) {
            D[par[i]].push_back(i);
        }
    }
}

這邊帶一個相關的題目

LOJ #3255. 「JOI 2020 Final」奥运公交

给 $n$ 點 $m$ 邊的有向圖，每條邊 $(u_i,v_i)$ 有邊權 $c_i$。你最多可以翻轉一條邊，翻轉代價是該條邊的 $d_i$，問從 $1$ 走到 $n$ 再走回 $1$ 的最小 cost

$n\le 200,m\le 5\times {10}^4$

思路

• 若翻轉的邊在 shortest path tree 上

  • 因為邊被刪掉了，整顆 tree 就要重算
  • $1\to u\to v\to n$
  • 你可以從 $1\to u$ 但這之後要走哪一條? (已經沒有 $u\to v$ 了)

• 若翻轉的邊不在 shortest path tree 上

  • 不經過邊: 原來的答案
  • 要經過邊 $1\to v\to u\to n\to 1$ 或 $1\to n\to v\to u\to 1$

• 我們只需要邊在 tree 上時再從新算一次 dijkstra

  • $O(n^3)$
  • $O(n)$ 樹上最多 $n-1$ 條邊
  • $O(n^2)$ 暴力 dijkstra

shortest path DAG

shortest path DAG結構

有的都建邊，有重邊時也可以使用，時常配合 DAG DP 計算方法數

實作

void build_dag() {
    for (int u = 1; u <= n; u++) {
        for (auto [v, w] : G[u]) {
            if (dis[v] == dis[u] + w) {
                D[u].push_back(v);
                in[v]++;
            }
        }
    }
}

LOJ #2350. 「JOI 2018 Final」月票购买

給一張 $n$ 點 $m$ 邊帶權無圖，從 $s$ 到 $t$ 選一條最短路徑，將其邊權都設為 $0$。問 $u$ 到 $v$ 的最短路徑最小可以是多少

$n\le {10}^5,m\le 2\times {10}^5$

思路

• 若有重疊，設重疊為 $x\to \dots \to y$

  • $ans=dis(u,x)+dis(y,v)\mathtt{\text{ or }}dis(u,y)+dis(x,v)$
  • 記得跟 $dis(u,v)$ 取 min

• 用 shortest path DAG 上枚舉 $x$ 用 dp 得到 $y$

  • DFS on DAG
  • $f[x]=$ topo sort 在 $x$ 之後的點的 $dis(v,y)$ 最小的 $y$

• 同理用 shortest path DAG 找 $g[x]=$topo sort 在 $x$ 之後的點 $dis(u,y)$ 最小的 $y$

• $ans=min(dis(u,x)+f[x],dis(v,x)+g[x],dis(u,v))$

code

void dfs(int u) {
    if (vis[u]) return;
    vis[u] = 1;
    f[u] = dV[u], g[u] = dU[u];
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (dS[u] + dT[v] + edge[i].len > dS[T]) continue;
        dfs(v);
        f[u] = min(f[u], f[v]), g[u] = min(g[u], g[v]);
    }
    ans = min({ans, f[u] + dU[u], g[u] + dV[u]});
}

LOJ #2344. 「JOI 2016 Final」铁路票价

給你一個 $n$ 點 $m$ 邊的無向圖，一開始每個邊的邊權都是 $1$，有 $q$ 個操作

• $\text{change}(i,2):$ 將第 $i$ 條邊邊權變成 $2$

每次操作完問有那些點跟原點的最短路不同

$n\le {10}^5,q,m\le 2\times {10}^5$

有用的測資

inputoutput

4 4 2
1 2 
2 3
1 4
4 3
2
1

0
2

思路

一樣先建立 shortest path DAG，刪邊時類似 topo sort。假如現在刪掉 $(u,v)$ 這條邊，若 $i{n}_v=0$ 就可以將變大傳遞給 $v$ 後面的點，由於每條邊邊權增加後就不可能出現在shortest path DAG，所以每條邊只需刪除一次故複雜度 $O(n+m)$。

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

int ans;

struct Edge {
    int u, v, w, id;
};

struct Graph {
    int n, m, s;
    vector<vector<Edge>> G;
    vector<vector<Edge>> D;
    vector<Edge> edges;
    vector<int> dis;
    vector<int> on_DAG;
    vector<int> in;

    Graph(int _n, int _m) {
        n = _n, m = _m;
        dis = vector<int>(n, INF);
        on_DAG = vector<int>(m);
        in = vector<int>(n);
        G.resize(n);
        D.resize(n);
    }

    void add_edge(int u, int v, int id) {
        int w = 1;
        G[u].pb({u, v, w, id});
        G[v].pb({v, u, w, id});
        edges.pb({u, v, w, id});
    }

    void dijkstra() {
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0, s});

        while (pq.size()) {
            auto [x, u] = pq.top();
            pq.pop();

            if (dis[u] != INF) continue;
            dis[u] = x;

            for (auto [u, v, w, id] : G[u]) {
                pq.push({w + dis[u], v});
            }
        }
    }

    void build_DAG() {
        for (int i = 0; i < n; i++) {
            for (auto [u, v, w, id] : G[i]) {
                if (dis[u] + w == dis[v]) {
                    D[u].pb({u, v, w, id});
                    on_DAG[id] = true;
                    edges[id] = {u, v, w, id};  // 要更新 edges 的方向
                    in[v]++;
                }
            }
        }
    }

    void del_edge(int eid) {
        if (on_DAG[eid] == false) return;

        queue<int> q;
        in[edges[eid].v]--;
        on_DAG[eid] = false;
        if (in[edges[eid].v] == 0) q.push(edges[eid].v);

        while (q.size()) {
            int u = q.front();
            q.pop();
            ans++;

            for (auto [u, v, w, id] : D[u]) {
                if (on_DAG[id] == false) continue;
                in[v]--;
                on_DAG[id] = false;
                if (in[v] == 0) {
                    q.push(v);
                }
            }
        }
    }
};

void work() {
    int n, m, q, s;
    cin >> n >> m >> q;
    Graph g(n, m);

    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        u--, v--;
        g.add_edge(u, v, i);
    }
    g.s = 0;

    g.dijkstra();
    g.build_DAG();

    while (q--) {
        int eid;
        cin >> eid;
        eid--;
        g.del_edge(eid);

        cout << ans << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        work();
    }
}

/*
4 4 2
1 2
2 3
1 4
4 3
2
1
*/

CS Academy - Chromatic Number

給一張 $n$ 點 $m$ 邊的圖，邊有邊權，請選擇 $k$ 個特殊點，使 $1\to n$ 有經過這 $k$ 個特殊點的最短路徑越多越好，輸出最多能有幾條這樣的路徑以及選法有幾種

$n\le 300,m\le \frac{n(n-1)}{2}$

思路

建圖

• $O(n^3)\mathtt{\text{ floyd warshall}}$
• $dis(u,v):$ $u$ 到 $v$ 的最短路
• $cnt(u,v):$ 從 $u$ 走最短路到 $v$ 有幾種走法

狀態定義

• $f_{i,k}$ 以 $i$ 結尾選 $k$ 個節點最多能在幾個 shortest path 上
• $g_{i,k}$ 以 $i$ 結尾選 $k$ 個節點有幾種選法能滿足在 $f_{i,k}$ 個 shortest path 上

轉移

• 找到 $u,v$ 滿足 $1\to v\to u\to n$
• $f_{u,k}=max\{\begin{array}{l}{f}_{v,k-1}\times cnt(v,u)\\ f_{u,k}\end{array}$
• $g_{u,k}$
  • $\mathtt{\text{if }}{f}_{v,k-1}\times cnt(v,u)\mathtt{\text{ == }}{f}_{u,k}:g_{u,k}=g_{u,k}+g_{v,k-1}$
  • $\mathtt{\text{else if }}{f}_{v,k-1}\times cnt(v,u)\mathtt{\text{ > }}{f}_{u,k}:g_{u,k}=g_{v,k-1}$

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 300 + 5;
const int M = 1e9 + 7;

int n, m, K;
int dis[maxn][maxn];
int cnt[maxn][maxn];
pii dp[maxn][maxn];

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dis[i][j] == dis[i][k] + dis[k][j]) {
                    cnt[i][j] += cnt[i][k] * cnt[k][j];
                } else if (dis[i][j] > dis[i][k] + dis[k][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                    cnt[i][j] = cnt[i][k] * cnt[k][j];
                }
            }
        }
    }
}

void init() {
    cin >> n >> m >> K;
    int u, v, w;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dis[i][j] = INF;
        }
        dis[i][i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        dis[u][v] = dis[v][u] = min(w, dis[u][v]);
        cnt[u][v] = cnt[v][u] = 1;
    }
}

void solve() {
    floyd();

    vector<pii> ord;
    for (int i = 1; i <= n; i++) {
        ord.pb({dis[1][i], i});
        cnt[i][i] = 1;
    }
    sort(ALL(ord));  // sort by distance

    // dp init
    for (int i = 0; i < n; i++) {
        int u = ord[i].S;
        if (dis[1][u] + dis[u][n] != dis[1][n]) continue;
        dp[u][1] = {cnt[1][u], 1};
    }

    // (v -> u) 一定是 v 先被走到再來才是 u，距離是一種可以判斷先後的好方法
    for (int i = 0; i < ord.size(); i++) {
        int u = ord[i].S;
        if (dis[1][u] + dis[u][n] != dis[1][n]) continue;  // check u

        for (int j = 0; j < i; j++) {
            int v = ord[j].S;
            if (dis[1][v] + dis[v][u] + dis[u][n] != dis[1][n])
                continue;  // check v

            for (int k = 2; k <= K; k++) {
                pii tmp;
                tmp.F = dp[v][k - 1].F * cnt[v][u];
                tmp.S = dp[v][k - 1].S;

                if (tmp.F > dp[u][k].F)
                    dp[u][k] = tmp;
                else if (tmp.F == dp[u][k].F) {
                    dp[u][k].S += tmp.S;

                    if (dp[u][k].S >= M)
                        dp[u][k].S -= M;
                }
            }
        }
    }

    pii res = {0, 0};
    // 以 u 結尾，還缺少到 u -> n 這段，補起來
    // 可是 n 結尾上面有算過了阿? 不一定會以 n 結尾 但最短路可延續至 n
    for (int i = 1; i <= n; i++) {
        if (dis[1][i] + dis[i][n] != dis[1][n])
            continue;

        dp[i][K].F *= cnt[i][n];

        if (dp[i][K].F > res.F)
            res = dp[i][K];
        else if (dp[i][K].F == res.F) {
            res.S += dp[i][K].S;

            if (res.S >= M)
                res.S -= M;
        }
    }

    cout << res.F << " " << res.S << "\n";
}

signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        init();
        solve();
    }
}

CSES - Visiting Cities

給 $n$ 點 $m$ 邊正權有向圖，從 $1\to n$ 判斷每個邊是否在每個最短路徑上

$n\le {10}^5,m\le 2\times {10}^5$

思路

建立 shotest path DAG，進行 DAG DP:

• $dp(1\to u):$ $1\to u$ 是最短路的路徑方法數

• $dp(u\to n):$ $u\to n$ 是最短路的路徑方法數

判斷 $dp(1\to u)\times dp(v\to n)==dp(s\to t)$，是話就是在最短路徑上

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>

using namespace std;

const int INF = 2e18;
const int MAXN = 3e5 + 5;
const int M = 2147483647;
int n, m;
vector<pii> G[MAXN];
vector<pii> R[MAXN];
vector<int> D[MAXN];
vector<int> P[MAXN];
int in[MAXN], rv[MAXN];

vector<int> dijkstra(int source, vector<pii> *G) {
    vector<int> dis(n + 1, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push({0, source});
    while (pq.size()) {
        auto [x, u] = pq.top();
        pq.pop();

        if (dis[u] != INF) continue;
        dis[u] = x;

        for (auto [v, w] : G[u]) {
            pq.push({x + w, v});
        }
    }
    return dis;
}

void build(vector<int> &dis) {
    for (int i = 1; i <= n; i++) {
        for (auto [v, w] : G[i]) {
            if (dis[v] == dis[i] + w) {
                D[i].push_back(v);
                P[v].push_back(i);
                in[v]++;
                rv[i]++;
            }
        }
    }
}

vector<int> topo(int source, int *in, vector<int> *D) {
    queue<int> q;
    vector<int> inn(n + 1);
    vector<int> dp(n + 1);
    dp[source] = 1;

    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) q.push(i);
        inn[i] = in[i];
    }

    while (q.size()) {
        int u = q.front();
        q.pop();

        for (auto v : D[u]) {
            dp[v] = (dp[v] + dp[u]) % M;
            inn[v]--;
            if (inn[v] == 0) q.push(v);
        }
    }

    return dp;
}

signed main() {
    cin >> n >> m;
    int u, v, w;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        R[v].push_back({u, w});
    }
    vector<int> dis = dijkstra(1, G);
    vector<int> rev = dijkstra(n, R);
    build(dis);

    vector<int> dp1 = topo(1, in, D);
    vector<int> dp2 = topo(n, rv, P);

    int tot = dp1[n];
    vector<int> res;
    for (int i = 1; i <= n; i++) {
        int cur = (dp1[i] * dp2[i]) % M;
        if (cur == tot) {
            res.push_back(i);
        }
    }

    cout << res.size() << "\n";
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
}

CSES - Visiting Cities 變化

給 $n$ 點 $m$ 邊正權有向圖，從 $1\to n$ 判斷每個邊是哪種 $\mathtt{\text{type}}$

• $\mathtt{\text{type 1: }}$是否在每個最短路徑上

• $\mathtt{\text{type 2: }}$至少有在一個最短路徑上

• $\mathtt{\text{type 3: }}$根本沒有在最短路徑上

$n\le {10}^5,m\le 2\times {10}^5$

思路

建立 shotest path DAG，進行 DAG DP

• $\mathtt{\text{type 1: }}$ 判斷 $dp(1\to u)\times dp(v\to n)==dp(s\to t)$

• $\mathtt{\text{type 2: }}$ 在 DAG 上的邊

• $\mathtt{\text{type 3: }}$ 不在 DAG 上的邊

建圖/分層

LOJ #3964. 「APIO2023」赛博乐园

給一張 $n$ 點 $m$ 無向圖，邊帶權，為 $c[i]$，一開始在點 $0$，你要去點 $t$。每個點有一個能力 $arr[i]$

• $arr[i]=0$，可讓當前已走的距離設為 $0$

• $arr[i]=1$，沒任何作用

• $arr[i]=2$，可讓當前已走的距離除以 $2$

除了點 $t$ 外，所有點都可以重複走，只要走到點就可使用 $arr[i]$，「除以 $2$ 」的能力總共只能使用 $k$ 次。只要抵達 $t$ 點就代表走到終點，問抵達 $t$ 點的最短距離

$n,m\le {10}^5,k\le {10}^6,c[i]\le {10}^9$

思路

我們可以將題目的圖反著做，即從點 $t$ 開始，跑回點 $0$，這樣就可以建立分層圖

• 原先遇到能力為 $0$ 的點，會把當前距離設置為 $0$

  • 那麼現在遇到能力為 $0$ 的點，相當於讓之後走過的所有邊權都變成 $0$

• 原先遇到能力為 $2$ 的點，會把當前距離減半

  • 那麼現在遇到能力為 $2$ 的點，相當於讓之後走過的所有邊權都變成原來的一半

第 $k$ 層為當前已使用「除以 $2$ 」的能力 $k$ 次。我們發現，直接讓第 $k$ 層上 $u$ 和 $v$ 之間的邊權為原圖上 $u$ 和 $v$ 之間邊權的 ${\displaystyle \frac{1}{2^k}}$ ，就能滿足能力為 $2$ 的點。

至於能力為 $0$ 的點，我們可以新建一層 $K+1$ 層，讓這一層內 $u$ 和 $v$ 之間的邊權都改成 $0$。然後讓所有 $arr[v]=0$ 的 node$(k,v)$ 直接建立單向邊到 $K+1$ 層即可。

• Node (u, k) → Node (v, k) 1/2^k

• Node (u, k) → Node (v, k) 0 if (k=K+1)

• Node (u, k) → Node (v, k+1) w * 1/2^(k+1) if arr[u]=2

• Node (u, k) → Node (u, K+1) 0 if arr[u]=0

我們發現，事實上用一些次優惠政策之後，最短路會變的很低，遠遠低於精度。具體來說，本題中最短路最大不超過邊數乘邊權最大值，即 ${10}^5\times {10}^9={10}^{14}$，只需讓這個數除以 $70$ 次 $2$ 就可以掉到 ${10}^{-7}$ 以下（$8\times {10}^{-8}$）

code

#include <bits/stdc++.h>

#include "cyberland.h"
#define pii pair<int, double>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const double INF = 1000000000000000.00;

struct Graph {
    int n, K, cnt;
    vector<vector<pii>> G;
    vector<vector<int>> id;
    vector<double> dis;
    vector<int> vis;

    void init(int _n, int _k) {
        n = _n, K = _k;
        id.resize(K + 1);
        cnt = 0;

        // (id + 1) % n == 0 -> cyberland
        // k != 0
        // id / n -> k
        for (int i = 0; i < K + 1; i++) {
            id[i].resize(n);
            for (int j = 0; j < n; j++) {
                id[i][j] = cnt++;  // id[k][u]
            }
        }
        G.resize(cnt);
        dis = vector<double>(cnt, INF);
        vis = vector<int>(cnt);
    }

    void add_edge(int u, int uk, int v, int vk, double w) {
        int id1 = id[uk][u];
        int id2 = id[vk][v];

        G[id1].pb({id2, w});
    }

    void dijkstra(int s) {
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
        pq.push({0, id[0][s]});  // cyberland 為起點
        dis[id[0][s]] = 0;

        while (pq.size()) {
            auto [dis_u, u] = pq.top();
            pq.pop();

            if ((u % n) == (s % n) && (u / n) != 0) continue;
            if (vis[u]) continue;
            vis[u] = 1;

            for (auto [v, w] : G[u]) {
                if ((v % n) == (s % n) && (v / n) != 0) continue;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    pq.push({dis[v], v});
                }
            }
        }
    }

    double cal() {
        double ans = INF;
        for (int i = 0; i < K + 1; i++) {
            int u = id[i][0];
            ans = min(ans, dis[u]);
        }
        if (ans == INF) return -1;

        return ans;
    }
};

/*
cyberland 不能去 relax 別人
Node (u, k) -> Node (v, k) 1/2^k
Node (u, k) -> Node (v, k) 0 if (k=K+1)
Node (u, k) -> Node (v, k+1) w * 1/2^(k+1) if arr[u]=2
Node (u, k) -> Node (u, K+1) 0 if arr[u]=0
*/

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    K = min(K, 70);
    vector<vector<pii>> G(N);
    for (int i = 0; i < M; i++) {
        int u = x[i], v = y[i], w = c[i];
        G[u].pb({v, w});
        G[v].pb({u, w});
    }
    K++;

    Graph g;
    g.init(N, K);

    double cnt = 1;
    for (int k = 0; k < K + 1; k++) {
        if (k == K) {
            for (int i = 0; i < N; i++) {
                for (auto [v, w] : G[i]) {
                    g.add_edge(i, k, v, k, 0);
                }
            }
            continue;
        }
        for (int i = 0; i < N; i++) {
            for (auto [v, w] : G[i]) {
                g.add_edge(i, k, v, k, (double)w * cnt);
            }
        }
        cnt *= 0.5;
    }
    cnt = 1;
    for (int k = 0; k < K - 1; k++) {
        cnt *= 0.5;
        for (int i = 0; i < N; i++) {
            for (auto [v, w] : G[i]) {
                if (arr[i] == 2) {
                    g.add_edge(i, k, v, k + 1, (double)w * cnt);
                    }
            }
        }
    }
    for (int k = 0; k < K; k++) {
        for (int i = 0; i < N; i++) {
            if (arr[i] == 0) {
                g.add_edge(i, k, i, K, 0);
            }
        }
    }

    g.dijkstra(H);

    return g.cal();
}

full code

#include <bits/stdc++.h>
#define pii pair<int, long double>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const long double INF = 1000000000000000.00;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

struct Graph {
    int n, K, cnt;
    vector<vector<pii>> G;
    vector<vector<int>> id;
    vector<double> dis;
    vector<int> vis;

    void init(int _n, int _k) {
        n = _n, K = _k;
        id.resize(K + 1);
        cnt = 0;

        // (id + 1) % n == 0 -> cyberland
        // k != 0
        // id / n -> k
        for (int i = 0; i < K + 1; i++) {
            id[i].resize(n);
            for (int j = 0; j < n; j++) {
                id[i][j] = cnt++;  // id[k][u]
            }
        }
        G.resize(cnt);
        dis = vector<double>(cnt, INF);
        vis = vector<int>(cnt);
    }

    void add_edge(int u, int uk, int v, int vk, double w) {
        int id1 = id[uk][u];
        int id2 = id[vk][v];

        G[id1].pb({id2, w});
    }

    void dijkstra(int s) {
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
        pq.push({0, id[0][s]});  // cyberland 為起點
        dis[id[0][s]] = 0;

        while (pq.size()) {
            auto [dis_u, u] = pq.top();
            pq.pop();

            if ((u % n) == (s % n) && (u / n) != 0) continue;
            if (vis[u]) continue;
            vis[u] = 1;

            for (auto [v, w] : G[u]) {
                if ((v % n) == (s % n) && (v / n) != 0) continue;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    pq.push({dis[v], v});
                }
            }
        }
    }

    double cal() {
        double ans = INF;
        for (int i = 0; i < K + 1; i++) {
            int u = id[i][0];
            ans = min(ans, dis[u]);
        }
        if (ans == INF) return -1;

        return ans;
    }
};

/*
cyberland 不能去 relax 別人
Node (u, k) -> Node (v, k) 1/2^k
Node (u, k) -> Node (v, k) 0 if (k=K+1)
Node (u, k) -> Node (v, k+1) w * 1/2^(k+1) if arr[u]=2
Node (u, k) -> Node (u, K+1) 0 if arr[u]=0
*/

double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    K = min(K, 70);
    vector<vector<pii>> G(N);
    for (int i = 0; i < M; i++) {
        int u = x[i], v = y[i], w = c[i];
        G[u].pb({v, w});
        G[v].pb({u, w});
    }
    K++;

    Graph g;
    g.init(N, K);

    double cnt = 1;
    for (int k = 0; k < K + 1; k++) {
        if (k == K) {
            for (int i = 0; i < N; i++) {
                for (auto [v, w] : G[i]) {
                    g.add_edge(i, k, v, k, 0);
                }
            }
            continue;
        }
        for (int i = 0; i < N; i++) {
            for (auto [v, w] : G[i]) {
                g.add_edge(i, k, v, k, (double)w * cnt);
            }
        }
        cnt *= 0.5;
    }
    cnt = 1;
    for (int k = 0; k < K - 1; k++) {
        cnt *= 0.5;
        for (int i = 0; i < N; i++) {
            for (auto [v, w] : G[i]) {
                if (arr[i] == 2) g.add_edge(i, k, v, k + 1, (double)w * cnt);
            }
        }
    }
    for (int k = 0; k < K; k++) {
        for (int i = 0; i < N; i++) {
            if (arr[i] == 0) g.add_edge(i, k, i, K, 0);
        }
    }

    g.dijkstra(H);

    return g.cal();
}

void init() {
    int n, m, k, h;
    cin >> n >> m >> k >> h;
    vector<int> arr(n);
    vector<int> x(n);
    vector<int> y(n);
    vector<int> c(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    for (int i = 0; i < m; i++) cin >> x[i] >> y[i] >> c[i];

    cout << fixed << setprecision(12) << solve(n, m, k, h, x, y, c, arr) << "\n";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        init();
    }
}

CSES - flight discount 變化

輸入一個 $n$ 點 $m$ 邊的有向圖，每條邊都有權重 $w(u,v)$。若連續走兩條邊 $a\to b\to c$，本來需花 $w(a,b)+w(b,c)$，使用優惠券可以將花費改成 $w(b,c)\times 2$，優惠券只能用 $k$ 次。問 $1\to n$ 的最小花費

思路

把圖複製 $k\times 2$ 層，三層三層一組，第 $k$ 層若原圖 $G$ 有邊 $(a,b,w_{a,b}),(b,c,w_{b,c})$ 就連接 $(a_k,b_{k+1},0),(b_{k+1},c_{k+2},2\times w_{b,c})$

2021 附中模競 II 惡地之路

給一張 $n$ 點 $m$ 邊無向圖，令 $s$ 到節點 $i$ 走 $k$ 步的最短距離是 $d(i,k)$，對於每個 $i$ 求 $min\{d(i,k)\times k\}$

$n\le 2000,m\le 3\times {10}^4$

思路

此方法並非滿分解，滿分解在這裡

---

把每個節點都複製 $n$ 份

如果本來有一條邊是 $(u,v)$，那就對所有 $1\le i<n$ 蓋

• $u$ 的第 $i$ 個點到 $v$ 的第 $i+1$ 個點（有向）
• $v$ 的第 $i$ 到 $u$ 的第 $i+1$ 個點（有向）

這樣走到某個節點的第 $i$ 個點的路徑長度一定是 $i-1$

$n^2$ 個點，$2nm$ 個邊做最短路徑，$O(nm\log nm)$

枚舉 $k=1\dots n$，對於第 $k$ 層拉出來求最小的 $di{s}_k$

$$ans=\underset{k=1\dots n}{min}\{di{s}_k\times k\}$$

2023 全國賽模擬賽 pI. 交通優惠券 (voucher)

給一張 n 點 m 邊的無向圖，邊有正權，有兩個特殊點 a, b，在經過特殊點後可將之後經過的一條邊免費，問 s 到 t 的最短路徑長度

$n\le 3\times {10}^5,m\le 5\times {10}^5$

思路

考慮只有一個特殊點時，有三種情況:

1. 還沒走到特殊點
2. 走到特殊點，還沒有使用優惠卷
3. 使用完優惠卷

我們可以建立三張圖，分別代表以上三種 case。將第一張圖的特殊點連一條邊到第二張圖的特殊點，代表已經可以使用優惠券了，再將第二張圖的每一個點連到第三張圖周圍的點，邊權為 0，走過去代表使用完了優惠券。

對於兩個特殊點的情況，我們定義好狀態 (x, y) 為經過 x 個特殊點，使用掉 y 個優惠卷。我們就用 (0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2) 這幾個狀態來建圖即可

CSES - flight discount

給一張 $n$ 點 $m$ 邊的無向圖，邊有權重，可將其中 $k$ 條邊以半價計算，求 $1\to n$ 的最短路

$n\le {10}^5,m\le 2\times {10}^5$

思路

原本 graph 有 $n$ 的點，變成一個圖有 $kn$ 個點的新 graph

$\mathtt{\text{node}}(k,u)$ 到 $\mathtt{\text{node}}(k,v)$ 的長度就是 $w(u,v)$

$\mathtt{\text{node}}(k-1,u)$ 到 $\mathtt{\text{node}}(k,v)$ 的長度就是 $w(u,v)/2$

直接跑 Dijkstra，起點 $\mathtt{\text{node}}(0,1)$ 終點 $\mathtt{\text{node}}(2,n)$

2023 TOI 一模 pD.安逸旅行路線 (jaunt)

有一張 $n$ 點 $m$ 邊有向圖，邊 $u\to v$ 的難度係數為 $d(u,v)$，代表如果 $u\to v$ 是路徑上的第 $k$ 條邊（1-based），則這條邊的辛苦程度是 $d(u,v{)}^k\mathrm{mod}P$，一條路徑的辛苦程度被定義為路徑上所有邊的最大辛苦程度。

輸出 $s$ 到 $t$ 的所有路徑中，最小辛苦程度的值，若不存在請輸出 $-1$。

$n\le 1000,m\le 5000,P\le {10}^5$ 且 $P$ 是質數

範測

sample1sample2sample3sample4

inputoutput

3 3 11 1 3
1 2 3
2 3 2
1 3 9

4

inputoutput

3 3 11 1 3
1 2 2
2 1 1
1 3 7

2

inputoutput

3 3 11 1 3
1 2 5
2 1 1
3 1 4

-1

inputoutput

2 6 94949 1 2
1 1 2
1 2 12345
1 2 23451
1 2 34512
1 2 45123
1 2 51234

1391

思路

根據費馬小定理，若 $p$ 是質數，且 $1\le d<p$，則 $d^{p-1}modp$ 一定是 $1$。

也就是說，這些邊的權重每 $p-1$ 步會循環一次。

我們可以建立一張新的圖，總共有 $(p-1)\times n$ 個節點。

node$(k,i)$ 的意義表示走完的步數 $mod(p-1)=k$，且停在原圖的節點 $i$。 新的 graph 會有 $(p-1)\times m$ 條邊。

若原圖有一個邊 $(u,v)$，則在新圖中，對所有的 $k$ 加上 node$(k,u)\to$ node$((k+1)mod(p-1),v)$ 的邊，權重是 $d(u,v{)}^{(k+1)mod(p-1)}modp$。

題目的目標是要讓最大邊權最小化，所以一種方法是二分答案 $X$，看看只走 $\le X$ 的邊是否從起點到終點 node$(k,t)$。

另一種方法是比較類似 MST 的 Prim 演算法。

先把設定 $X=1$，看看有沒有能走到 node$(k=0\sim (p-2),t)$ 任意一個節點，

如果不行就放寬 $X=2$，再看看能多走哪些。

如果不行就放寬 $X=3$，再看看能多走哪些。

一直放寬到可以走到 node$(k=0\sim (p-2),t)$ 任一個節點。

這題的邊權重會介於 $[0,p-1]$，所以 priority_queue 可以用開 $p-1$ 個 vector 的方式來實作，讓 push / pop 時間只要 $O(1)$。

整個圖的邊數量有 $(p-1)\times m$，總時間複雜度也是 $(p-1)\times m$。

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 1e3 + 5;
const int M = 1e9 + 7;

struct node {
    int u, k, dis;
};

struct DS {
    vector<vector<node>> pq;
    int max_val = 0, threshold = 0;

    void init(int _max_val) {
        max_val = _max_val;
        pq = vector<vector<node>> (max_val + 1);
    }

    void push(node x) {
        pq[max (threshold, x.dis)].pb(x);
    }

    node get_value() {
        while (threshold <= max_val && pq[threshold].size() == 0) threshold++;

        if (threshold <= max_val && pq[threshold].size() > 0) {
            node ret = pq[threshold].back();
            pq[threshold].pop_back();
            return ret;
        }
        else return {-1, -1, -1};
    }
} pq;

int n, m, P, s, t;
vector<pii> G[maxn];
int vis[maxn][maxn];

int fpow(int a, int b, int p) {
    int ret = 1;
    while (b != 0) {
        if (b & 1) ret = (ret * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ret;
}

int Prim() {
    pq.init(P - 1);
    // k = [0, p - 2] k = 0 為開始那層
    pq.push({s, 0, 0});
    int fg = 0;
    while (true) {
        auto [u, k, dis] = pq.get_value();
        if (u == -1) break;
        if (vis[u][k] == 1) continue;
        vis[u][k] = 1;
        if (u == t) {
            fg = 1;
            break;
        }
        for (auto [v, w] : G[u]) {
            int vk = (k + 1) % (P - 1);
            int wk = fpow(w, (k + 1) % (P - 1), P);

            pq.push({v, vk, wk});
        }
    }
    if (fg == 1) return pq.threshold;
    return -1;
}

void init() {
    cin >> n >> m >> P >> s >> t;
    int u, v, w;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        G[u].pb({v, w});
    }
}

void work() {
    cout << Prim() << "\n";
} 

signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        init();
        work();
    }
} 

CF 1422 D. Returning Home

在 $n\times n$ 的 grid 上，給起點終點，還有 $m$ 個特殊點，每秒可以上下左右走一格，只要與特殊點同一個 row 或 col，可以不花時間直接傳送到特殊點，問到達終點的最少時間

$n\le {10}^9,m\le {10}^5$

提示

grid 的性質 : 兩點間的距離為曼哈頓距離

思路

把特殊點所在的行和列當作點

1. 特殊點向它們所在的行和列連雙向邊，花費都為 0
2. 起點向它所在的行列連邊，花費都為 0
3. 終點跟所有特殊點連邊，邊權為曼哈頓距離
4. 出現的行之間連雙向邊，花費為兩行之間的距離
5. 出現的列之間連雙向邊，花費為兩列之間的距離
6. 起點與終點連邊，邊權為曼哈頓距離

最後的答案記得跟起點直接到終點的答案取 min

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

struct Graph {
    vector<vector<pii>> G;
    int n = 0;

    int add_node() {
        n++;
        G.pb({});
        return n - 1;
    }

    void add_edge(int u, int v, int w) {
        G[u].pb({v, w});
    }

    int dijkstra(int s, int t) {
        vector<int> dis(n, INF);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0, s});
        dis[s] = 0;

        while (pq.size()) {
            auto [dis_u, u] = pq.top();
            pq.pop();
            if (dis[u] < dis_u) continue;
            dis[u] = dis_u;

            for (auto [v, w] : G[u]) {
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    pq.push({dis[v], v});
                }
            }
        }
        return dis[t];
    }
};

/*
1. 特殊點向它們所在的行和列連雙向邊，花費都為 0
2. 起點與終點向它所在的行列連邊
3. 出現的行之間連雙向邊，花費為兩行之間的距離
4. 出現的列之間連雙向邊，花費為兩列之間的距離
5. 起點與終點連邊，邊權為 |x_s - x_t| + |y_s - y_t|
*/
int n, m;
pii s, t;
vector<pii> special;
vector<int> X, Y;
int id_X[maxn], id_Y[maxn], id_Special[maxn];
int id_start, id_end;

void init() {
    cin >> n >> m;
    cin >> s.F >> s.S >> t.F >> t.S;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        special.pb({x, y});
        X.pb(x);
        Y.pb(y);
    }
    X.pb(s.F);
    X.pb(t.F);
    Y.pb(s.S);
    Y.pb(t.S);
}

void work() {
    Graph g;
    sort(ALL(X));
    X.resize(unique(ALL(X)) - X.begin());
    sort(ALL(Y));
    Y.resize(unique(ALL(Y)) - Y.begin());

    for (int i = 0; i < m; i++) {
        id_Special[i] = g.add_node();
    }

    map<int, int> mpx, mpy;

    for (int i = 0; i < X.size(); i++) {
        id_X[i] = g.add_node();
        mpx[X[i]] = id_X[i];
    }

    for (int i = 0; i < Y.size(); i++) {
        id_Y[i] = g.add_node();
        mpy[Y[i]] = id_Y[i];
    }
    id_start = g.add_node();
    id_end = g.add_node();

    for (int i = 0; i < m; i++) {
        g.add_edge(id_Special[i], mpx[special[i].F], 0);
        g.add_edge(mpx[special[i].F], id_Special[i], 0);
    }

    for (int i = 0; i < m; i++) {
        g.add_edge(id_Special[i], mpy[special[i].S], 0);
        g.add_edge(mpy[special[i].S], id_Special[i], 0);
    }

    for (int i = 0; i < X.size(); i++) {
        if (i > 0) {
            g.add_edge(id_X[i], id_X[i - 1], X[i] - X[i - 1]);
            g.add_edge(id_X[i - 1], id_X[i], X[i] - X[i - 1]);
        }
    }

    for (int i = 0; i < Y.size(); i++) {
        if (i > 0) {
            g.add_edge(id_Y[i], id_Y[i - 1], Y[i] - Y[i - 1]);
            g.add_edge(id_Y[i - 1], id_Y[i], Y[i] - Y[i - 1]);
        }
    }

    g.add_edge(id_start, mpx[s.F], 0);
    g.add_edge(id_start, mpy[s.S], 0);

    for (int i = 0; i < m; i++) {
        int cost = abs(special[i].F - t.F) + abs(special[i].S - t.S);
        g.add_edge(id_Special[i], id_end, cost);
    }

    g.add_edge(id_start, id_end, abs(s.F - t.F) + abs(s.S - t.S));

    cout << g.dijkstra(id_start, id_end) << "\n";
}

signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        init();
        work();
    }
}

CF 1846 G. Rudolf and CodeVid-23

以下提到的 $01$ bit-string 長度皆為 $n$。給一個 $01$ bit-string，代表目前有的症狀，有 $m$ 個藥可以使用，每個藥有緩解的 $01$ bit-string $a_i$，與副作用 $01$ bit-string $b_i$，與花費 $d_i$。每種藥吃完即消失。問最少花費使所有症狀消失

$n\le 10,m\le 1000$

思路

這題的關鍵是能不能想出可以用圖論的觀點看。

將每種 $01$ bit-string 的狀態看成一個點，依照題意將狀態之間連有向邊，邊權為 $d_i$，答案就是從一開始的 $01$ bit-string 到 $0$ 的最短路

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<long long, long long>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

struct data {
    int a, b, d;
} a[maxn];

struct Graph {
    vector<vector<pii>> G;
    int n = 0;

    int add_node() {
        n++;
        G.pb ({});
        return n - 1;
    }

    void add_edge(int u, int v, int w) {
        G[u].pb({v, w});
    }

    int dijkstra(int s, int t) {
        vector<int> dis (n, INF);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push ({0, s});
        dis[s] = 0;

        while (pq.size ()) {
            auto [dis_u, u] = pq.top(); pq.pop();
            if (dis[u] < dis_u) continue;
            dis[u] = dis_u;

            for (auto [v, w] : G[u]) {
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    pq.push ({dis[v], v});
                }
            } 
        }
        if (dis[t] == INF) return -1;
        return dis[t];
    }
    void clear() {
        for (int i = 0; i < n; i++) {
            G[i].clear();
        }
    }
} g;

int n, m;
int now;
int id[(1 << 20)];

void init() {
    cin >> n >> m;
    string s;
    cin >> s;
    now = 0;
    for (int i = n - 1; i >= 0; i--) {
        now += (s[i] - '0') * (1 << i);
    }
    for (int t = 0; t < m; t++) {
        cin >> a[t].d;
        string s1, s2;
        cin >> s1 >> s2;
        a[t].a = 0, a[t].b = 0;
        for (int i = n - 1; i >= 0; i--) {
            a[t].a += (s1[i] - '0') * (1 << i);
        }
        for (int i = n - 1; i >= 0; i--) {
            a[t].b += (s2[i] - '0') * (1 << i);
        }
    }
}

void solve() {
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < m; i++) {
            int S = mask & (((1 << 20) - 1) ^ a[i].a);
            S |= a[i].b;
            g.add_edge(id[mask], id[S], a[i].d);
        }
    } 
    int ans = g.dijkstra(id[now], id[0]);
    cout << ans << '\n';
}

signed main() {
    for (int mask = 0; mask < (1 << 20); mask++) {
        id[mask] = g.add_node();
    } 
    int t = 1;
    cin >> t;
    while (t--) {
        g.clear();
        init();
        solve();
    }
} 

建立虛點

JOI 2021 Final - Robot

給一張 $n$ 點 $m$ 邊無向圖，邊有顏色 $c_i$ 與權值 $w_i$，每條邊可花 $P_i$ 變顏色（只限變一次）。想從 $u$ 走到 $v$ 若且唯若 $u$ 的鄰邊只有 $u\to v$ 有該種顏色。問從 $1$ 走到 $n$ 的最小花費。

$n\le {10}^5,m\le 2\times {10}^5,1\le c_i\le m,1\le w_i\le {10}^9$

範例

思路

令一個點 u 他周圍顏色為 c 的 w 總和為 $S_{u,c}$。我們首先可以想到，對於 u 走到 v，若 (u, v) 的顏色 distinct，那我們的花費就是 0；否則，我們有兩種方法:

1. 改變 (u, v) 本身的顏色，花費為 $w$

2. 改變跟 (u, v) 同色的邊，花費為 $S_{u,c}-w$

這樣就結束了嗎，不盡如此。我們發現當走了 A 到 B 到 C，滿足 (A, B) 與 (B, C) 的顏色皆相同，且 (A, B) 是走 case 1，而 (B, C) 是走 case 2，那我們中間的邊會重複算。

以上圖來說，第一次以 A 為中心，對 (A, B) 用 case1 算了 w(A, B)；而第二次以 B 為中心，對 (B, C) 用 case2 算了 w(B, H) + w(B, G) + w(A, B)。發現到 w(A, B) 被重複算兩次。

解決的方法，我們可以建立幫每個點的每個顏色都建立虛點，假設今天是 $B$ 點的虛點 $B_c$，就直接將 $A\to B_c$ 的權重設為 0，而 $B_c\to C$ 的權重設為 $S_{B,c}-w(B,C)$。

---

Q1: 對於 case1，為何一定找的到一種顏色來換?

A1: 因為邊最多只有 m 條，而顏色有 m 種，不管怎麼樣至少一定有一種顏色沒被挑到。

Q2: 會不會在進行 case2 時，將某條邊 e 換掉了我們等等要用的顏色後，等等需要用到 e 時，所收到的顏色是錯誤的?

A2: 不會，如果待會還要用到，那不如在目前這一步直接用 case1 走 e 就好。

code

#include <bits/stdc++.h>
#define ALL(v) begin(v), end(v)
#define All(v, l, r) &v[l], &v[(r) + 1]
using i64 = int64_t;
using db = double;
using std::cin;
using std::cout;
constexpr int N = 1e5 + 5, M = 5e5 + 5;
constexpr i64 inf = 1e18;

int n, m, vt;
std::array<std::map<int, std::vector<std::pair<int, i64> > >, N> vec;
std::array<std::map<int, i64>, N> sum;
std::array<std::vector<std::pair<int, i64> >, M> G;

namespace Dij {
std::array<i64, M> dis;
std::array<bool, M> vis;
std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int> >, std::greater<std::pair<i64, int> > > q;

auto dij(int s) {
    std::fill(All(dis, 1, vt), inf);
    q.emplace(0, s), dis[s] = 0;

    while (!q.empty()) {
        auto u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, w] : G[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) q.emplace(dis[v], v);
            }
        }
    }
    return (dis[n] == inf ? -1 : dis[n]);
}
}

auto main() -> int {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m, vt = n;
    for (auto i = 1, u = 0, v = 0, w = 0, c = 0; i <= m; ++i) {
        cin >> u >> v >> c >> w;
        vec[u][c].emplace_back(v, w), vec[v][c].emplace_back(u, w);
        sum[u][c] += w, sum[v][c] += w;
    }
    for (auto u = 1; u <= n; ++u) {
        for (auto [c, cur] : vec[u]) {
            auto s = sum[u][c];
            vt++;
            for (auto [v, w] : cur) {
                if (cur.size() == 1)
                    G[u].emplace_back(v, 0);
                else
                    G[u].emplace_back(v, std::min(w, s - w));
                G[v].emplace_back(vt, 0), G[vt].emplace_back(v, s - w);
            }
        }
    }

    cout << Dij::dij(1) << "\n";
    return 0;
}

USACO Gold 2021 January - Telephone

給 $n$ 跟一個 $k\times k$ 的 matrix $S$，每個點有一個權值 $b_i$。$i$ 能走到 $j$ 當且僅當 $S_{b[i],b[j]}=1$，花費 $\text{cost}=|i-j|$。求從 $1\to n$ 最少要多少 $\text{cost}$

$n\le 5\times {10}^4,k\le 50,1\le b_i\le k$

思路

【觀察】:

顯然 $O(n^2)$ 的複雜度我們無法接受，考慮到 k 只有 50，我們從這裡下手。觀察到 $\text{cost}=|i-j|\to$ 可以想成每次都移動 $1$ 格，也就是 從 $i\to i+1\mathtt{\text{ or }}i-1$。

一個點 i 要走到 j，我們只需要去看他的 b[i] 與 b[j] 即可，優點是他們的範圍在 [1, k]。

【作法: 分層圖】:

依照範圍，我們猜到大概是要建一個 $O(nk)$ 的分層圖。我們想一下 node(u, b) 會代表的是什麼，u 一定是當前的點，而 b 我們依照上面的觀察可以得知就是上一個點的 b[i]。具體來說，u 代表目前的位置（不是真正在 u，而是目前的 cost 增加或減到 u），b 代表從上個真正點的 $b_i$。轉移如下:

node(u, b) = $\{\begin{array}{l}\mathtt{\text{node(u + 1, b)}}+1\\ \mathtt{\text{node(u - 1, b)}}+1\\ \mathtt{\text{node(u, b[u])}}+0\end{array}$

其中 node (u, b) -> node (u, b[u]) 代表的是從虛點走到真正 u 的點。我們就可以做 dijkstra 了。

LOJ #2335. 「JOI 2017 Final」足球

有 $n$ 個球員站在 Grid 上求球從 $a_1$ 踢到 $a_n$ 的最小 $cost$

• 球員踢球(上下左右) $A\times p+B$

• 球員移動(上下左右) $cost=C$

• 放下球 $cost=0$

• 拿起球 $cost=0$

思路

• $0,1,2,3$ 上下左右 (自飛)

• $4$ 停止 (自飛)

• $5$ 帶飛 (往 random direction)

• 自飛的球

  • 繼續移動 $0,1,2,3\to 0,1,2,3:A$ 往自己的方向
  • 被球員撿到 $4\to 5:di{s}_{i,j}\times C$
    • $di{s}_{i,j}$ 為最近的球員到 $(i,j)$ 的距離
  • 停下來 $0,1,2,3\to 4:0$

• 帶飛的球

  • 繼續跟著球員走 $5\to 5:C$ 四個方向
  • 被球員踢出去 $5\to 0,1,2,3:B$
  • 停下來 停下來，撿起來，浪費時間

CF 1860 E. Fast Travel Text Editor

給一個字串 S，每個相鄰兩個字母叫一個位置，有 q 筆詢問從位置 s → t 的最少操作次數是多少。一次操作可執行以下三個選項之一：

• 往左移一格

• 往右移一格

• 傳送到同樣的相鄰兩個字母同樣的位置

$2\le |S|\le 5\times {10}^4,1\le q\le 5\times {10}^4$

思路

觀察 : 相鄰字串的組合只有 26 * 26 種，可以建圖做 dijkstra

考慮建邊，對於一個位置，他可以 :

• 傳送到相同的字串，cost = 1

• 往左走或往右走，cost = 1

因為在相同的字串之間建完全圖太費時了，我們考慮對於每種字串組合都建一個虛點，分別與同種字串組合的 node 連邊。考慮邊權，當從一個 index $i$ 走到虛點再走到 index $j$ 會花 cost = 1 很難實作，我們不如將與虛點連接的邊權都設為 1，最後答案再除以 2 就好了，這麼做的話往左走或往右走的邊權也要設為 2。

考慮 query 的部分，每次重跑一次 dijkstra 會太久，我們可以分成兩種 case，有至少做一次傳送與完全沒做傳送。

有做一次傳送我們就可以枚舉有做傳送的虛點，答案就是 dis(s → 虛點) + dis(虛點 → t) 再除以 2。（因為一定只能透過相同字串組合的點進去虛點，所以可以保整有經過兩次）。到虛點的部分可以預處理所有虛點當起點的 dijkstra。

完全沒做的部分就直接算 index s 跟 index t 的距離就好了

類似題 : https://codeforces.com/contest/1301/problem/F

code(from abc)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
const int mod = 998244353, N = 6e4, M = 26 * 26;

int dis[M][N];
vector <pii> adj[N];

void build(int s, int id) {
    fill(dis[id], dis[id] + N, N);
    queue <int> q;
    dis[id][s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto [u, w] : adj[v]) if (dis[id][u] > dis[id][v] + w) {
            dis[id][u] = dis[id][v] + w;
            q.push(u);
        }
    }
}

void solve() {
    string s;
    cin >> s;
    int n = s.length();
    for (int i = 0; i < n - 1; ++i) {
        int x = (s[i] - 'a') * 26 + (s[i + 1] - 'a') + n; // 虛點
        adj[i].emplace_back(x, 1), adj[x].emplace_back(i, 1);
    }
    for (int i = 0; i + 2 < n; ++i) { // 相鄰的建邊
        adj[i].emplace_back(i + 1, 2), adj[i + 1].emplace_back(i, 2);
    }
    for (int i = 0; i < M; ++i) { // 預處理
        build(i + n, i);
    }
    int q; cin >> q;
    while (q--) {
        int s, t; cin >> s >> t, --s, --t;
        int ans = abs(s - t);
        for (int i = 0; i < M; ++i) {
            ans = min(ans, (dis[i][s] + dis[i][t]) / 2);
        }
        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

JOI 2024 Final 建设工程 2

給一張 $n$ 點 $m$ 邊無向圖，第 $i$ 條邊為 $(u_i,v_i)$，邊權 $w_i$。問有幾種 pair$(u,v)$ 滿足 $u<v$ 且在 $u,v$ 之間建一條邊權 $\ell$ 的雙向邊，可以使起點 $s$ 到終點 $t$ 的最短路距離 $\le k$

$n,m\le 2\times {10}^5,1\le \ell ,w_i\le {10}^9,1\le k\le {10}^{15}$

思路

首先，若 $\text{dis}(s\to t)$ 一開始就已經 $\le k$，那我們的方法數就直接輸出 ${\displaystyle \frac{n(n-1)}{2}}$。否則，我們的想法就是找到滿足能從 $s\to u\to v\to t$ 的條件數，就是先用 Dijkstra 建出 $\text{dis}(s\to u)$ 與 $\text{dis}(t\to v)$，然後再想辦法用枚舉 $u$，$v$ 用二分搜之類的來計算。但此時會不會發生我們能從 $s\to u\to v\to t$ 且能從 $s\to v\to u\to t$ 的 $(u,v)$ 呢? 因為那會導致我們重複計算。我們來先試著列式一下，看這種情況存不存在：

證明：從 $s\to u\to v\to t$ 或 $s\to v\to u\to t$ 皆可是存在的

$$\begin{array}{rl}& \{\begin{array}{l}\text{dis}(s\to u)+\ell +\text{dis}(v\to t)\le k\\ \text{dis}(s\to v)+\ell +\text{dis}(u\to t)\le k\end{array}\\ \Rightarrow & \{\begin{array}{l}\text{dis}(s\to u)+\text{dis}(v\to t)\le k-\ell \\ \text{dis}(s\to v)+\text{dis}(u\to t)\le k-\ell \end{array}\\ \Rightarrow & \text{dis}(s\to u)+\text{dis}(v\to t)+\text{dis}(s\to v)+\text{dis}(u\to t)\le 2k-2\ell \end{array}$$

由於 $\text{dis}(s\to t)>k$

$$\begin{array}{rl}& min\{\text{dis}(s\to u)+\text{dis}(u\to t),\text{dis}(s\to v)+\text{dis}(s\to t)\}>k\\ \Rightarrow & \{\begin{array}{l}\text{dis}(s\to u)+\text{dis}(u\to t)>k\\ \text{dis}(s\to v)+\text{dis}(s\to t)>k\end{array}\\ \Rightarrow & \text{dis}(s\to u)+\text{dis}(u\to t)+\text{dis}(s\to v)+\text{dis}(v\to t)>2k\end{array}$$

代表 $2k\le 2k-2\ell$，這只會在 $\ell <0$ 成立，但我們 $1\le \ell \le {10}^9$，所以無法成立，代表結果矛盾的，不存在這種情況。所以我們就只需要算 $s\to u\to v\to t$ 的 $(u,v)$ 數量就好，完全不用考慮重複算的問題。這個有很多種作法，以下提供兩種：

1. 可以先把 $\text{dis}(t\to v)$ sort 好，然後固定 $u$，去二分搜滿足條件的 $v$。
2. 或是可以先把 $\text{dis}(s\to u),\text{dis}(t\to u)$ 都由小到大分別 sort 好，然後因為滿足的 pair 具有單調性，可以用 two pointer 算，具體見代碼。

code

#include <bits/stdc++.h>
#define int long long

using namespace std;
using pii = pair<int, int>;

const int N = 2e5 + 5;
int n, m, s, t, l, k;
int ans, ds[N], dt[N];
bool vis[N];
vector<pii> G[N];

void dij(int dis[], int s) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        auto [sum, u] = q.top();
        q.pop();
        if (vis[u]) {
            continue;
        }
        vis[u] = 1;
        for (auto [v, w] : G[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> s >> t >> l >> k;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    memset(ds, 0x3f, sizeof(ds));
    memset(dt, 0x3f, sizeof(dt));
    dij(ds, s), dij(dt, t);

    if (ds[t] <= k) {
        cout << n * (n - 1) / 2 << '\n';
        return 0;
    }

    sort(ds + 1, ds + 1 + n);
    sort(dt + 1, dt + 1 + n);

    int j = 0;
    for (int i = n; i >= 1; i--) {
        while (ds[i] + l + dt[j + 1] <= k && j < n) {
            j++;
        }
        ans += j;
    }
    cout << ans << '\n';
    return 0;
}

次短路

第二次跑到某個點的時候就代表那個點的次短路

次短路實作

void dijkstra (int s) {
    priority_queue<pii, vector<pii>, greater<pii>> pq; 
    pq.push({0, s});

    while (pq.size()) {
        auto [sum, u] = pq.top();
        pq.pop();

        if (ans[u].f == -1) {
            ans[u].f = sum;
        } else if (ans[u].s == -1) {
            if (sum == ans[u].f) continue;// 嚴格要加這行
            ans[u].s = sum;
        } else {
            continue;
        }

        for (auto [v, w] : G[u]) {
            pq.push({sum + w, v});
        }
    }
}

模板 USACO 2006 NOV Roadblocks G

給一張 n 點 m 邊帶權無向圖，問 n 到 1 的嚴格次短路

$n\le 5000,m\le {10}^5$

嚴格次短路方法數 AcWing - 383.觀光

給一張 $n$ 點 $m$ 邊有向帶權圖，求 $s\to t$ 的 :

• 最短路方法數

• 比最短路多一單位的方法數

$N\le 1000,M\le {10}^4,$ 有 $T$ 筆測資

思路

$d{p}_f(v)=\sum _{f(v)+w(v,u)==f(u)}d{p}_f(u)$

$d{p}_g(v)=\sum \{\begin{array}{ll}d{p}_g(u)& \text{ if }g(v)+w(v,u)==g(u)\\ d{p}_f(u)& \text{ if }f(v)+w(v,u)==g(u)\end{array}$

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

struct Edge {
    int u, v, w;
};

struct Graph {
    int n, m, s, t;
    vector<vector<Edge>> G;
    vector<int> f, g;
    vector<int> dp_f, dp_g;

    Graph(int _n, int _m) {
        n = _n, m = _m;
        f = vector<int>(n, INF);
        g = vector<int>(n, INF);
        dp_f = vector<int>(n);
        dp_g = vector<int>(n);
        G.resize(n);
    }

    void add_edge(int u, int v, int w) {
        G[u].pb({u, v, w});
    }

    void sec(int u, int x) {
        if (f[u] < x && g[u] == INF)
            g[u] = x;
        else if (f[u] < x && x < g[u])
            g[u] = x;
    }

    void dijkstra() {
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push({0, s});

        while (pq.size()) {
            auto [x, u] = pq.top();
            pq.pop();

            if (f[u] != INF) continue;
            f[u] = x;

            for (auto [u, v, w] : G[u]) {
                pq.push({w + f[u], v});
            }
        }
    }

    int find_second_best() {
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        vector<int> vis(n);
        for (int i = 0; i < n; i++) {
            for (auto [u, v, w] : G[i]) {
                sec(v, f[i] + w);
            }
        }

        for (int i = 0; i < n; i++) {
            pq.push({g[i], i});
        }

        while (pq.size()) {
            auto [x, u] = pq.top();
            pq.pop();

            if (vis[u]) continue;
            vis[u] = 1;

            for (auto [u, v, w] : G[u]) {
                sec(v, x + w);
                pq.push({g[v], v});
            }
        }
    }

    void build_DAG(vector<int> &dis, vector<vector<Edge>> &D) {
        for (int i = 0; i < n; i++) {
            for (auto [u, v, w] : G[i]) {
                if (dis[u] + w == dis[v]) {
                    D[u].pb({u, v, w});
                }
            }
        }
    }

    void topo(vector<int> &dp, vector<vector<Edge>> &D) {
        vector<int> in(n);
        for (int i = 0; i < n; i++) {
            for (auto [u, v, w] : D[i]) {
                in[v]++;
            }
        }

        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.push(i);
        }

        while (q.size()) {
            int u = q.front();
            q.pop();

            for (auto [u, v, w] : D[u]) {
                in[v]--;
                dp[v] += dp[u];
                if (in[v] == 0) q.push(v);
            }
        }
    }

    int solve() {
        int res = 0;

        dijkstra();
        vector<vector<Edge>> Df(n);
        build_DAG(f, Df);
        dp_f[s] = 1;
        topo(dp_f, Df);

        res += dp_f[t];
        find_second_best();
        if (g[t] == INF || g[t] != f[t] + 1) return res;

        vector<vector<Edge>> Dg(n);
        vector<vector<Edge>> Dfg(n);

        build_DAG(g, Dg);

        // f[u] -> w -> g[v]
        for (int i = 0; i < n; i++) {
            for (auto [u, v, w] : G[i]) {
                if (f[u] + w == g[v]) {
                    dp_g[v] += dp_f[u];
                }
            }
        }
        topo(dp_g, Dg);

        res += dp_g[t];
        return res;
    }
};

void work() {
    int n, m, s, t;
    cin >> n >> m;
    Graph g(n, m);

    int u, v, w;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        u--, v--;
        g.add_edge(u, v, w);
    }
    cin >> s >> t;
    s--, t--;
    g.s = s, g.t = t;

    cout << g.solve() << "\n";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        work();
    }
}

TIOJ 2204.交替路徑

給一張 $n$ 點 $m$ 邊的簡單無向圖，每一條邊有兩個權重長度 $w_i$，顏色 $c_i$。定義「交替路徑」為沒有相鄰兩條邊有相同顏色的路徑(不一定是簡單路徑)。求全點對最短「交替路徑」長

$n\le 500,m\le \frac{n(n-1)}{2}$

思路

因為只需考慮相鄰的邊，我們只要看結尾的顏色

考慮 $i\to j$ 是一條最短交替路徑，現在我想要從 $j$ relax 周圍的點，我一定是拿最短的嘛！

除非某條邊 $j\to k$ 的顏色和 $i\to j$ 的結尾顏色一樣

這個時候一定是拿「結尾顏色不一樣的次短交替路徑」

所以只需要維護最短的與次短的，並確保結尾顏色不相同

使用 $n^2$ dijkstra 實作，最短的與次短當成兩個不同的點來看

詳見代碼

code

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int mod2 = 5e8 + 4;
const int M = 1e9 + 7;

int n, m;

struct Edge {
    int u, v, w, c;
};

struct triple {
    int a, b, c;
};

struct Node {
    int c1 = -1, c2 = -1, dis1 = INF, dis2 = INF, vis1, vis2;
    // c1, dis1 : 當前最短交替路徑的顏色, 長度
    // c1, dis1 : 當前與最短顏色不同的交替路徑的顏色, 長度
    // vis1, vis2 : 是否已經固定 (被拿來 relax 起他人)
    // c != -1, vis = 0 已入堆, 尚未固定
};

struct Graph {
    vector<vector<Edge>> G;

    void init() {
        vector<vector<Edge>>().swap(G);
        G.resize(n);
    }

    void add_edge(int u, int v, int w, int c) {
        G[u].pb({u, v, w, c});
        G[v].pb({v, u, w, c});
    }

    vector<int> dijkstra(int s) {
        vector<Node> node(n);
        node[s].c1 = 0;
        node[s].dis1 = 0;

        auto sec = [&](int u, int dis, int c) {
            if (node[u].vis1 == 0) {
                if (dis < node[u].dis1) {
                    if (c != node[u].c1) {
                        node[u].dis2 = node[u].dis1;
                        node[u].c2 = node[u].c1;
                    }
                    node[u].dis1 = dis;
                    node[u].c1 = c;
                    return;
                }
            }

            if (node[u].vis2 == 0) {
                if (dis < node[u].dis2) {
                    if (c != node[u].c1) {
                        node[u].dis2 = dis;
                        node[u].c2 = c;
                    }
                }
            }
        };
        auto find = [&]() {
            int u = -1, c, dis = INF, ord;
            for (int i = 0; i < n; i++) {
                if (node[i].vis1 == 0 && node[i].c1 != -1) {
                    if (node[i].dis1 < dis) {
                        u = i, c = node[i].c1, dis = node[i].dis1;
                        ord = 1;
                    }
                }
                if (node[i].vis2 == 0 && node[i].c2 != -1) {
                    if (node[i].dis2 < dis) {
                        u = i, c = node[i].c2, dis = node[i].dis2;
                        ord = 2;
                    }
                }
            }
            if (u == -1) return (triple){-1, -1, -1};

            if (ord == 1)
                node[u].vis1 = 1;
            else
                node[u].vis2 = 1;

            return (triple){u, dis, c};
        };

        for (int i = 1; i <= 2 * n - 1; i++) {
            auto [u, dis, c] = find();
            if (u == -1) break;

            for (auto [u, v, ew, ec] : G[u]) {
                if (c != ec) sec(v, dis + ew, ec);
            }
        }

        vector<int> dis(n);
        for (int i = 0; i < n; i++) {
            if (node[i].vis1 == 0)
                dis[i] = 0;
            else
                dis[i] = node[i].dis1;
        }

        return dis;
    }
} G;

void init() {
    cin >> n >> m;

    G.init();
    int u, v, w, c;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w >> c;
        u--, v--;
        G.add_edge(u, v, w, c);
    }
}

void work() {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        vector<int> dis = G.dijkstra(i);
        for (int j = 0; j < n; j++) {
            ans = (ans + ((i + j + 2) * dis[j]) % M) % M;
        }
    }

    cout << (ans * mod2) % M << "\n";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        init();
        work();
    }
}

K 短路

dijkstra 正確性證明

你把狀態 $w$ 推出去的時候 狀態 $<w$ 都已經推出去了

所以當 $w$ 被推出去的時候 就保證是最佳解

延伸 : A*、 yen's algorithm

每個點跑進去 k 次即可

K 短路 code

void dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii>> pq; //{val,id}
    pq.push({0, s});

    while (pq.size()) {
        int sum = pq.top().f, u = pq.top().s;
        pq.pop();

        if (dis[u].size() >= k) continue;
        dis[u].pb(sum);

        for (auto [v, w] : G[u])
            pq.push({sum + w, v});
    }
}

模板 CSES - Flight Routes

給一張 $n$ 點 $m$ 邊的有向正權圖，$1$ 為起點，問起點到終點 $n$ 的前 $k$ 短路

$n\le {10}^5,m\le 2\times {10}^5$

線段樹優化建圖

詳見此處

練習題

CF 1051 F.The Shortest Statement

給一個 $n$ 點 $m$ 邊的無向圖，$q$ 筆詢問 :

• $s_i\to t_i$ 的最短路徑

$n,m,q\le {10}^5,m-n\le 20$

思路

觀察到 $m-n\le 20$

若 $m=n-1$ 那就是一顆樹，我們可以將最短路分成全部都在樹上，跟有走到非樹邊的情況

全部都在樹上 :

樹上最短路，LCA

有走到非樹邊 :

因為這種邊最多只有 $21$ 條，也就是涵蓋 $42$ 個點，所以我們可以暴力以這 $42$ 個點為源點跑 dijkstra

$s\to u\to t$，我們枚舉這 $42$ 個 $u$

CF 715 B. Complete The Graph

給一張 $n$ 點 $m$ 邊無向圖，其中有一些邊要你指定權重

求是否有方案使得從 $s\to t$ 的最短路恰為 $L$，輸出這些邊指定後的權重，或無法達成

$n\le 1000,m\le {10}^4,L\le {10}^9$

思路

接下來說的「邊」都指代「邊權未知的邊」。

將所有邊都設為 $L+1$，如果 $dis(s,t)<L$ ，那麼必然無解

將所有邊都設為 $1$ ，如果 $dis(s,t)>L$ ，那麼必然無解

考慮將任意一條邊的權值 $+1$，則 $dis(s,t)$ 會 $+0$ 或者 $+1$

如果將所有邊按照「隨便」一個順序不斷 $+1$，直到所有邊的權值都是 ${10}^9$ 了，那麼在這個過程中，$dis(s,t)$ 是遞增的，而且一定在某一個時刻 $dis(s,t)=L$

這樣的話我們就可以二分答案 + dijkstra解決這個問題了

時間複雜度 $\log (mL)\times m\log m=O(m\log m\log (mL))$

---

考慮邊權皆為 $1$ 的最短路，邊權皆為 INF 的最短路，有解若且唯若 $L$ 在這兩個值之間

邊權皆為 $x$ 可得出最短路具有單調性

小數點二分搜 $x$，將每個邊權都設為 $x$，使最短路比 $L$ 大一點點

建立 shortest path DAG，將其中一條路徑向下取整，其他邊權即設為 INF

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

struct Edge {
    int u, v, w, id;
};

struct Graph {
    int run = 0;
    int n, m, s, t, L;
    vector<Edge> edges;
    vector<int> dis;
    vector<vector<pii>> G; // {w, v}

    Graph (int n, int m, int s, int t, int L) : n(n), m(m), s(s), t(t), L(L) {}

    void add_edge (int u, int v, int w, int id) {
        edges.pb ({u, v, w, id});
    }

    int dijkstra () {
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.push ({0, s});

        while (pq.size ()) {
            auto [sum, u] = pq.top(); pq.pop();

            if (dis[u] != INF) continue;
            dis[u] = sum;

            for (auto [w, v] : G[u]) {
                pq.push ({sum + w, v});
            }
        }
        return dis[t];
    }

    int check (int x) {
        //   0 1 2 3
        //   4 5 6 7
        // x = [m - 1, 10^9 * m - 1]
        // 進行了 cnt=x/m 輪
        // x %= m
        // [0, x] +(cnt+1)
        // [x + 1, m - 1] +(cnt)
        G = vector<vector<pii>>(n, vector<pii>());
        dis = vector<int>(n, INF);

        int cnt = x / m;
        x %= m;

        for (auto [u, v, w, id] : edges) {
            if (w == 0) {
                if (id <= x) {
                    G[u].pb ({cnt + 1, v});
                } 
                else G[u].pb ({cnt, v});
            }
            else G[u].pb({w, v});
        }

        return dijkstra();
    }
}; 

int n, m, L, s, t;

void work () {
    cin >> n >> m >> L >> s >> t;
    Graph g(n, m, s, t, L);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.add_edge(u, v, w, i);
        g.add_edge(v, u, w, i);
    }

    int l = m - 1, r = (1e9) * m - 1;
    while (l < r) {
        int mid = (l + r) / 2;

        if (g.check(mid) < L) l = mid + 1;
        else r = mid;
    }
    int dis = g.check (l);
    if (dis != L) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";

    map<pii, int> mp;
    for (int i = 0; i < n; i++) {
        for (auto [w, v] : g.G[i]) {
            if (mp[{i, v}] || mp[{v, i}]) continue;
            cout << i << " " << v << " " << w << "\n";
            mp[{i, v}] = true;
        }
    }
} 

signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        work();
    }
} 

全國賽模擬賽 2022 pD. 小風的遊戲 (Game)

給一張 $n$ 點 $m$ 邊無向圖，目標是讓 $s$ 到 $t$ 的最短路徑長度恰好為 $d$。給一個 $1\dots m$ 的 permutation $p$，代表 $w_{p_1}<w_{p_2}<\dots <w_{p_m}$，問是否有辦法構造 $w_1,\dots ,w_m$，有的話請輸出

$n\le {10}^5,m\le 2\times {10}^5,1\le d\le {10}^{11}$

思路

最小的解就是 $w_{p_1}=1,w_{p_2}=2,\dots$，我們二分搜一個 threshold $t$，滿足使用邊權 $\le t$ 的邊恰能使 $s\to t$ 的最短路 $\le d$，若全部的邊都用上 $d$ 還是小於最短路 $L$，就輸出無解。

接下來我們要來調整，讓最短路變成恰好 $d$。因為到 $w_i=t$ 才恰好形成 <= d 的最短路，所以 $w_i=t$ 一定在最短路徑上，而在這之前，最短路是 > d 的。如果我們將 $w_i$ 改成 $t+d-L$，可以使得最短路加起來恰好變成 $d$（因為沒有 $w_i$ 這條邊的路徑，權值一定 > d）。至於剩下的邊我們要使他們不會干預我們的最短路徑。$<t$ 的邊維持不變，因為上面的有最短路徑的圖就有涵蓋這些邊，也就是 $1,2,\dots$；$>t$ 的邊要保證不會出現在最短路徑上，就要設為 $d+1,d+2,\dots$。

d = 7

CF 1307 D. Cow and Fields

給定一個 $n$ 個點 $m$ 邊無向圖，$n$ 個點中有 $k$ 個是特殊點，可以在這 $k$ 個點中找兩個點連一條無向邊。每條邊的距離都是 $1$。問從 $1$ 到 $n$ 的最短路最大是多少。

$n,m,k\le 2\times {10}^5$

思路

現在有兩個點 $i$ 和 $j$ ，如果其建邊的話，最短路可能是 $1\to i\to j\to n$ 或者 $1\to j\to i\to n$。這樣代表的距離也就是 $dis(1\to i)+dis(j\to n)+1$ 和 $dis(1\to j)+dis(i\to n)+1$ 了。我們要取最小的，因此 $dis(1\to i)+dis(j\to n)+1<dis(1\to j)+dis(i\to n)+1$ 時，才符合最短路的條件。移項後變為 $dis(1\to i)-dis(i\to n)<dis(1\to j)-dis(j\to n)$。依據 exchange argument，按照這個條件由小到大排序後，枚舉位於後面的點 $j$，然後找到點 $j$ 前面的 $dis(1\to i)$ 的最大值，這樣可以保證相加之和是最大的。最大就是之前的最短路了。最後與原圖最短路比較一下就可以了。

Bellman Ford/SPFA

Bellman Ford

Bellman-Ford 就是把所有節點都 relax，做 $n-1$ 次，會對的原因是最短路徑最多只經過 $n-1$ 條邊

模板 CSES - Cycle Finding

給一張 $n$ 點 $m$ 邊有向圖，求上面是否有負環，如果有的話輸出任意負環

$n\le 2500、m\le 5000$

算法實作

int x; // 看第 n 輪是否會 relax
for (int i = 0; i < n; ++i) {
    x = -1; // 沒 relax
    for (auto &e: edges) {
        if (distances[e.v] > distances[e.u] + e.w) {
            distances[e.v] = distances[e.u] + e.w;
            parents[e.v] = e.u;
            x = e.v; // 有 relax
        }
    }
}

code

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Edge {
    int u, v, w;
};

int n, m;
vector<Edge> edges;
vector<int> distances;
vector<int> parents;

vector<int> construct_answer(int x) {
    for (int i = 0; i < n; ++i) {
        x = parents[x];
    }

    vector<int> ans;
    int y = x;
    do {
        ans.push_back(y);
        y = parents[y];
    } while (x != y);

    ans.push_back(x);
    reverse(ans.begin(), ans.end());

    return ans;
}

signed main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        edges.push_back({u, v, w});
    }
    parents = vector<int>(n);
    distances = vector<int>(n);
    int x; // 看第 n 輪是否會 relax
    for (int i = 0; i < n; ++i) {
        x = -1; // 沒 relax
        for (auto &e: edges) {
            if (distances[e.v] > distances[e.u] + e.w) {
                distances[e.v] = distances[e.u] + e.w;
                parents[e.v] = e.u;
                x = e.v; // 有 relax
            }
        }
    }
    if (x != -1) {
        auto ans = construct_answer(x);
        cout << "YES" << '\n';
        for (int i = 0; i < ans.size(); ++i) {
            cout << ans[i] + 1 << ' ';
        }
    } else {
        cout << "NO" << '\n';
    }
}

SPFA

介紹

全名為 Shortest Path Finding Algorithm。屬於單源最短路，為 Bellman Ford 的優化版本，每回合只更新「前一回合有被鬆弛」的點相鄰的邊，實作上類似 dijkstra。如果要做很多次最短路，圖每次都變化，就可以用 SPFA，例如 MCMF，複雜度平均 $O(n+m)$，worst case $O(nm)$，含運氣成分

概念(BFS)

如果上一輪某一個點的距離沒有更新,那這一輪也沒必要 relax 他。把距離有更新的節點丟進 queue 裡,然後一直拿 queue 裡的節點出來 relax。由於 BFS 處理環能力較弱，若遇到負環可能 TLE

SPFA BFS code

bool SPFA(int s) {
    vector<int> dis(n, INF);
    vector<bool> inq(n);
    vector<int> cnt(n);

    queue<int> q;
    q.push(s);
    dis[s] = 0;
    inq[s] = true;

    while (q.size()) {
        int u = q.front();
        q.pop();
        cnt[u]++;

        if (cnt[u] == n) {
            // negative cycle
            return true;
        }

        inq[u] = false;

        for (auto [v, w] : G[u]) {
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;

                if (!inq[v]) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }

    return false;
}

概念(DFS)

如果一個 relax 操作是在 back edge 上進行的，則有負環。DFS 處理最短路能力較若弱，一般針對負環的題目¹。

若在判斷負環的題目時，會將 dis[ ] 初始值設為 0，使一開始正權的邊沒辦法走下去，減少額外的時間。

SPFA DFS code

int n, m;
int dis[maxn];
bool inq[maxn];
vector<pii> G[maxn];

bool spfa(int u) {
    inq[u] = true;
    for (auto [v, w] : G[u]) {
        if (dis[u] + w < dis[v]) {
            dis[v] = dis[u] + w;
            if (inq[v] || spfa(v)) {
                return true;
            } 
        }
    }
    inq[u] = false;
    return false;
} 

bool check() {
    for (int i = 0; i < n; i++) {
        dis[i] = 0;
        inq[i] = false;
    }

    for (int i = 0; i < n; i++) {
        if (!inq[i]) {
            if (spfa(i)) return true;
        }
    }
    return false;
}

題目

最小平均環 LOJ #10084. 「一本通 3.3 练习 1」最小圈

給一張 $n$ 點 $m$ 邊有向圖，邊有權重，定義平均環為

$$\mu (C)={\displaystyle \frac{\sum w_{u,v}}{|C|}}$$

求最小平均環 ${\mu }^{\ast }(C)=min\{\mu (C)\}$

$n\le 3000,m\le {10}^4,|w_{i,j}|\le {10}^7$

思路

假設所求的平均最小值為 X，環上各個邊的權值分別為 A1,A2...Ak，可以得到 :

X=(A1+A2+A3+...+Ak)/K

A1+A2+A3+...+Ak=X*K

移項可得：(A1-X)+(A2-X)+(A3-X)+...+(Ak-X)=0

即判斷：(A1-ans)+(A2-ans)+(A3-ans)+...+(Ak-ans)<=0

最後問題就變成了二分一個最大的 ans 滿足邊權為 w - ans 的圖不存在負環

實作上需要使用 DFS SPFA，不然會 TLE

code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const double INF = 2e18;
const int maxn = 3000 + 5;
const int M = 1e9 + 7;
const double EPS = 1e-10;

int n, m;
double dis[maxn];
int vis[maxn];
vector<pair<int, double>> G[maxn];

bool spfa(int u, double t) {
    vis[u] = true;
    for (auto [v, w] : G[u]) {
        w -= t;
        if (dis[u] + w < dis[v]) {
            dis[v] = dis[u] + w;
            if (vis[v] || spfa(v, t)) {
                return true;
            } 
        }
    }
    vis[u] = false;
    return false;
} 

bool check(double t) {
    for (int i = 0; i < n; i++) {
        dis[i] = 0;
        vis[i] = false;
    }

    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            if (spfa(i, t)) return true;
        }
    }
    return false;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v; double w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].pb({v, w});
    }

    double l = -1e7, r = 1e7;
    while (r - l > EPS) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    cout << fixed << setprecision(8) << l << '\n';
} 

在看下面全國賽的題目前，我們先來看一道題目（與 Bellman-Ford 無關）

LeetCode 134. Gas Station

有兩個長度為 n 的環狀陣列，cost[i] 表示從 i^th 到 (i+1)^th 路上會消耗的汽油量，gas[i] 表示你站在 i^th 可以得到的汽油量，選擇一個起點使得在走完一圈的過程中不能沒油

思路

我們可以將 c[i] 表示為 gas[i] - cost[i]，要能繞完一圈的前提是 c[1]+...+c[n] >= 0

這邊不懂可以看這個影片

假設起點為 k，令 suf[i] 為 c[i]+...+c[n]，那麼 k 是一個合法的起點若且唯若

• i = k...n 這段不能為負

• i = 1...(k - 1) 不能為負

也就是可表示成

• suf[k] - suf[i] >= 0

• suf[k] + (suf[1] - suf[i]) >= 0

顯然，suf[k] 越大越好，所以我們只需找 suf 最大的點即可

code

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int mx = -1e9, suf = 0, start = -1;
        for (int i = gas.size()-1; i >= 0; i--) {
            suf += gas[i] - cost[i];

            if (suf > mx) {
                mx = suf;
                start = i;
            }
        }

        return (suf >= 0) ? start : -1;
    }
};

從上面的題目我們可以觀察到以下性質

非負環必存在至少一個起點 $u$，過程中權重和都 $\ge 0$，且 suf 最大的必定滿足

非負環 $\Rightarrow$ suf[1] >= 0

suf[k] = max (suf)

因為 suf[k] 是最大的，所以 suf[k] - suf[i] 至少 >= 0

• suf[k]+(suf[1] - suf[i]) >= 0

• suf[k] - suf[i] >= 0

如何找非負環 ?

讓每個邊減一個數 $ϵ$，使得正環 $1$ 還是正的，而零環可以變負環，那環上至多 $n$ 個點，若 $ϵ=\frac{1}{n}$ 那就會使 $1\to 0$，而若減掉 $ϵ=\frac{1}{n+1}$ 那就會使 $1$ 變成 $0.\cdots$ 還是正的，零環會變 $-0.\cdots$ 是負的

全國賽 2021 pC

給一張 $n$ 點（城市） $m$ 邊的有向圖 $G_0$。 我們對 $G_0$ 的每條邊都加上 $k$ 個點（村莊），得到一張 $n+mk$ 節點的有向圖 $G$，並賦予點權重 $c:V(G)\to Z$（每個節點的收支）。

設 $C$ 是 $G$ 上的一個簡單環且 $u\in V(C)$。 若從 $u$ 出發沿著 $C$ 走一圈，任意前綴點權重和都 $\ge 0$，我們就說 $C$ 是 $G$ 的一個好環，而 $u$ 是 $C$ 的一個好起點。

請找出 $G$ 的任一個好環 $C$ 與 $C$ 的任一個好起點 $u$，並求出 $C$ 上有幾個點可以當作好起點，這些好起點又有幾個在 $G_0$ 上。

$k\le n\le 2000,m\le 8000$

思路 (from twpca)

見 twpca

Floyd warshall

模板 CSES - Shortest Routes II

給一張無向圖，$q$ 筆詢問求某兩點間的最短路徑

$n\le 500,q\le {10}^5$

算法實作

// init
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == j) dis[i][j] = 0;
        else if (adj[i][j] != INF) dis[i][j] = adj[i][j];
        else dis[i][j] = INF;
    }
}

// floyd warshall
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }
    }
}

最小環

TIOJ 1212.圖論之最小圈測試

給一張 $n$ 點 $m$ 邊有向圖，找一个最小權值和的環（Girth）

$3\le n\le 500,m\le {10}^5$

第一個想法是 Dijkstra，我們可以枚舉每條邊，移除該邊然後跑一次 dijkstra，更新此環的總和 $dis(u,v)+w$ 到答案，複雜度 $O(n^2\log n)$

第二個想法是 Floyd warshall，Floyd warshall 有個性質，在最外層迴圈 $k$ 開始時，$di{s}_{i,j}$ 僅考慮是 $[1,k)$ 的最短路，我們可以利用這性質讓環成為 $di{s}_{i,j}+w(i,k)+w(k,j)$，因為環上一定有一個節點編號最大的點，故正確性足夠。

網路上有一個作法是直接將初始狀態 dis[i][i] 設為 INF，也可以 AC，但若圖改成無向圖（洛谷 P6175 无向图的最小环问题）就不能用了。但上面兩種做法依然可實用

實作

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;

const int INF = 2e18;
const int maxn = 500 + 5;
const int M = 1e9 + 7;

int n, m;
int adj[maxn][maxn];
int dis[maxn][maxn];

int solve() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) dis[i][j] = 0;
            else if (adj[i][j] != INF) dis[i][j] = adj[i][j];
            else dis[i][j] = INF;
        }
    }

    int ans = INF;
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i < k; i++) {
            for (int j = 1; j < k; j++) {
                if (i != j) {
                    ans = min(ans, dis[i][j] + adj[j][k] + adj[k][i]);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    if (ans == INF) return 0;
    return ans;
}

signed main() {
    while(cin >> n >> m) {
        if (n == 0 && m == 0) break;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                adj[i][j] = INF;
            }
        }
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v;
            adj[u][v] = 1;
        }
        cout << solve() << '\n';
    }
} 

zerojudge b686. 6. 航線規劃

給一張 $n$ 點 $m$ 邊無向圖，邊帶權，每個點有一個權重 $a_i$

有 $q$ 筆詢問，如下 :

• $x,s,t:$ $A_i<x$ 的點都不能走，問 $s\to t$ 的最短路徑
  

$n\le 500,m\le {10}^5,q\le 2\times {10}^5,1\le a_i,x,s,t\le n$

思路

code

sort (A.rbegin(), A.rend()); // 防禦力大到小
sort (query.rbegin(), query.rend()); // 破壞力大到小

for (int q = 1; q <= query.size(); q++) {
    int w = query[q];

    // floyd 中繼點並非一次全部更新, 而是要得才更新
    for (int k = 1; A[k] > w; k++) {
       for (int i = 1; i <= n; i++) {
           for (int j = 1; j <= n; j++) {
               d[i][j] = max (d[i][j], d[i][k] + d[k][j]);
           }
       } 
    }
}

TIOJ 1034.搶救雷恩大兵 (Saving Ryan)

給 $N\times N$ 的 grid，每個點都有權值

$Q$ 筆詢問 :

• 可以把一個點的權值改成 $0$ 的狀況下，$s_i\to t_i$ 的最短路最少是多少

$N\le 20,Q\le N^4$

思路

建表，對於每筆 query 枚舉中間點即可

2021 一模 pA.挑選路徑(Shortcut)

定義一張圖的總花費是所有點對之間的最短距離總和。給定一張 $n$ 點 $m$ 邊的簡單無向連通圖，在你可以加一條邊的情況下，和原圖相比最多可以減少多少總花費？又有幾種加邊的方式可以減少那麼多花費？

$3\le n\le 500,n-1\le m\le {\displaystyle \frac{n(n-1)}{2}}-1$

思路

【暴力作法: $O(n^5)$】

$O(n^2)$ 枚舉要加的邊，每次重新做 $n$ 次 BFS（一次 $O(n+m)$ ）或是 Floyd-Warshall

【列算式，預處理: $O(n^4)$】

每次枚舉要加的邊 $(u,v)$ 時，計算每個點對的距離減少了多少，也就是 $\sum _{i<j}max\{0,\text{dis}(i,j)-(\text{dis}(i,u)+1+\text{dis}(v,j)),\text{dis}(i,j)-(\text{dis}(i,v)+1+\text{dis}(u,j))\}$，其中 $\text{dis}(i,j)$ 是原圖中 $i$ 與 $j$ 的最短距離，可以 $O(n^3)$ 預處理。

【滿分解: $O(n^3)$】

我們來證明看看是否從兩邊過來的路徑都存在（仿造 2024 JOI pB），假設 $\text{dis}(i\to j)=k$：

證明：從 $i\to u\to v\to j$ 或 $i\to v\to u\to j$ 皆存在更短的路徑

$$\begin{array}{rl}& \{\begin{array}{l}\text{dis}(i\to u)+\ell +\text{dis}(v\to j)\le k\\ \text{dis}(i\to v)+\ell +\text{dis}(u\to j)\le k\end{array}\\ \Rightarrow & \{\begin{array}{l}\text{dis}(i\to u)+\text{dis}(v\to j)\le k-\ell \\ \text{dis}(i\to v)+\text{dis}(u\to j)\le k-\ell \end{array}\\ \Rightarrow & \text{dis}(i\to u)+\text{dis}(v\to j)+\text{dis}(i\to v)+\text{dis}(u\to j)\le 2k-2\ell \end{array}$$

而 $\text{dis}(i\to u)+\text{dis}(u\to j)$ 或 $\text{dis}(i\to v)+\text{dis}(v\to j)$ 至少都會大於等於 $k$（因為 $i$ 到 $j$ 的最短路是 $k$），假設是 $\text{dis}(i\to u)+\text{dis}(u\to j)\ge k$，這樣的話另外一條 $\text{dis}(i\to v)+\text{dis}(v\to j)$ 一定 $\le k-2\ell$，因為這題 $\ell =1$，我們發現最短路居然更短了，矛盾，所以只會存在一條。

也就是說，我們在算總花費減少多少的時候可以改為計算 $\sum _{i,j}max\{0,\text{dis}(i,j)-(\text{dis}(i,u)+1+\text{dis}(v,j))\}$，注意這裡的 $(i,j)$ 是無序的。這種要枚舉好幾個變數的我們會想要試著枚舉其中幾個，另外一個使用類似資料結構優化。考慮固定 $i,v$，那麼 $j,u$ 之間是獨立的，我們可以拆成 $max\{0,(\text{dis}(i,j)-\text{dis}(v,j)-1)-\text{dis}(i,u)\}$。問題就變成，對於每個 $a_u$，求 $\sum _{j}max\{0,b_j-a_u\}$ 的總和。這可以用 counting sort + two pointer 在線性時間內解決，具體來說，就是用一個 bucket 先預處理好對於每個數字 $t$，$b_j\ge t$ 的 $b_j$ 總和，與有幾個符合的 $b_j$，對於 $a_u$ 就是去看 $\text{sum}(t)-\text{cnt}(t)\cdot a_u$。總複雜度是枚舉所有 $i,v$ 所需的 $O(n^2)$，接著 $O(n)$ 枚舉 $j$ 去預處理 bucket，然後在預處理好後再 $O(n)$ 對於每個 $u$ 查表計算，所以整體複雜度就是 $O(n^2\cdot (n+n))=O(n^3)$。

參考: https://omeletwithoutegg.github.io/2021/09/22/toi-2021-sols/#p1-shortcut

code

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int MAXN = 505, inf = 1e9;

int dis[MAXN][MAXN];
int ans[MAXN][MAXN];
int sum[MAXN];
int cnt[MAXN];
int n, m;

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                dis[i][j] = inf;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        dis[u][v] = dis[v][u] = 1;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int v = 0; v < n; v++) {
            for (int j = 0; j < n; j++) {
                sum[j] = cnt[j] = 0;
            }
            for (int j = 0; j < n; j++) {
                int d = dis[i][j] - dis[v][j] - 1;
                if (d < 0) continue;
                cnt[d] += 1;
                sum[d] += d;
            }
            for (int j = n - 1; j >= 0; j--) {
                sum[j] += sum[j + 1], cnt[j] += cnt[j + 1];
            }
            for (int u = 0; u < v; u++) {
                int d = dis[i][u];
                ans[u][v] += sum[d] - cnt[d] * d;
            }
        }
    }

    int mx = -1;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (ans[i][j] == mx) {
                cnt++;
            } else if (ans[i][j] > mx) {
                mx = ans[i][j], cnt = 1;
            }
        }
    }
    cout << cnt << ' ' << mx << '\n';
}
/*
5 4
1 2
2 3
3 4
2 5

5 5
1 2
2 3
3 4
4 5
5 1
*/

---

參考資料

• https://drive.google.com/file/d/1a1mgK8KFJWNoXATHwi3E6ceStn22QmZl/view

• https://drive.google.com/file/d/1q2mP9uHYAauroE2mjtYKti9khs0H9qaJ/view

• https://slides.com/peter940324/deck-f0e69c#/3/18

• IOIC 2023

• sprout 2023

---

1. 這是筆者從中國博客抄來的，不知道實際上實不實用。 ↩