1. 云图网首页
  2. 技术专区
  3. 编程笔记

最短路小结

• 编程笔记


单源最短路径

DIjkstra 算法

auto Dijkstra = [&](int s)
{
    std::priority_queue<PII, std::vector<PII>, std::greater<PII>> q;
    std::vector<int> dis(n + 1, inf), vis(n + 1);
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (auto [v, w] : g[u])
        {
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
    return dis;
};

SPFA 算法

auto SPFA = [&](int s)
{
    std::queue<int> q;
    std::vector<int> dis(n + 1, inf), inq(n + 1);
    dis[s] = 0;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (auto [v, w] : g[u])
        {
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!inq[v])
                    q.push(v), inq[v] = true;
            }
        }
    }
    return dis;
};

任意两点间距离

Floyd 算法

auto Floyd = [&](std::vector<std::vector<int>> &f)
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                f[i][j] = std::min(f[i][j], f[i][k] + f[k][j]);
};

应用汇总

分层图

一般模型：在一个正常的图上可以进行 /(k/) 次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以转换状态了。

一般有两种方法解决分层图最短路问题：

  • 建图时直接建成 /(k+1/) 层跑最短路。

  • 仿照动态规划思想，多开一维记录机会信息。

通信线路

解法一：

建 /(k+1/) 层图，在从一个点到另一个点时，如果选择走边权为 0 的边，就进入下一层，相当于进行一次免费操作。共有 /((k+1) /times n/) 个点， /(1 /sim n/) 表示第一层， /((1+n) /sim (n+n)/) 代表第二层， /((1+2 /times n) /sim (n+2 /times n)/) 代表第三层， /((1+i /times n)/sim(n+i /times n)/) 代表第 /(i+1/) 层。答案就是 /(n , 2 /times n, 3 /times n /dots i /times n/) 中的最小值。

最短路小结

#include <bits/stdc++.h>
#define IOS                           /
    std::ios::sync_with_stdio(false); /
    std::cin.tie(0);                  /
    std::cout.tie(0);
#define PII std::pair<int, int>

const int inf = 0x3f3f3f3f;

int main()
{
    IOS;
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<PII>> g((k + 1) * n + 1);
    for (int i = 1, x, y, z; i <= m; ++i)
    {
        std::cin >> x >> y >> z;
        for (int j = 1; j <= k + 1; ++j)
        {
            g[(j - 1) * n + x].push_back({(j - 1) * n + y, z});
            g[(j - 1) * n + y].push_back({(j - 1) * n + x, z});
            if (j != k + 1)
            {
                g[(j - 1) * n + x].push_back({j * n + y, 0});
                g[(j - 1) * n + y].push_back({j * n + x, 0});
            }
        }
    }
    auto dijkstra = [&](int st)
    {
        std::vector<int> vis, dis;
        vis = dis = std::vector<int>((k + 1) * n + 1);
        std::fill(dis.begin(), dis.end(), inf);
        dis[st] = 0;
        std::priority_queue<PII, std::vector<PII>, std::greater<PII>> q;
        q.push({0, st});
        while (!q.empty())
        {
            int u = q.top().second;
            q.pop();
            if (vis[u])
                continue;
            vis[u] = true;
            for (auto [v, w] : g[u])
            {
                w = std::max(dis[u], w);
                if (dis[v] > w)
                {
                    dis[v] = w;
                    q.push({dis[v], v});
                }
            }
        }
        int res = inf;
        for (int i = 1; i <= k + 1; ++i)
            res = std::min(res, dis[i * n]);
        if (res == inf)
            res = -1;
        return res;
    };
    std::cout << dijkstra(1) << std::endl;
    return 0;
}

解法二：

  • dis[i][j] 代表到达 i 用了 j 次免费机会的最小花费。

  • vis[i][j] 代表到达 i 用了 j 次免费机会的情况是否出现过。

如果存在一条从 /(x/) 到 /(y/) 长度为 /(z/) 的无向边，有下列转移方程：

  • /(dis[y][p] = max(dis[x][p], z)/)

  • /(dis[y][p] = dis[x][p-1]/)

前者表示不在边 /((x,y,z)/) 上使用免费机会，后者表示使用。

#include <bits/stdc++.h>
#define IOS                           /
    std::ios::sync_with_stdio(false); /
    std::cin.tie(0);                  /
    std::cout.tie(0);
#define PII std::pair<int, int>

const int inf = 0x3f3f3f3f;

struct node
{
    int x, y, z;
    friend bool operator<(node lft, node rht) { return lft.y > rht.y; };
};

int main()
{
    IOS;
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<PII>> g(n + 1);
    for (int i = 1, x, y, z; i <= m; ++i)
    {
        std::cin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    auto dijkstra = [&](int st)
    {
        std::vector<std::vector<bool>> vis(n + 1, std::vector<bool>(k + 1));
        std::vector<std::vector<int>> dis(n + 1, std::vector<int>(k + 1, inf));
        for (int i = 1; i <= k; ++i)
            dis[0][i] = 0;
        dis[st][0] = 0;
        std::priority_queue<node> q;
        q.push({st, 0, 0});
        while (!q.empty())
        {
            node now = q.top();
            q.pop();
            int u = now.x, p = now.z;
            if (vis[u][p])
                continue;
            vis[u][p] = true;
            for (auto [v, w] : g[u])
            {
                w = std::max(dis[u][p], w);
                if (dis[v][p] > w)
                {
                    dis[v][p] = w;
                    q.push({v, dis[v][p], p});
                }
                if (p < k && dis[v][p + 1] > dis[u][p])
                {
                    dis[v][p + 1] = dis[u][p];
                    q.push({v, dis[v][p + 1], p + 1});
                }
            }
        }
        int ans = inf;
        for (int i = 0; i <= k; ++i)
            ans = std::min(ans, dis[n][i]);
        return ans == inf ? -1 : ans;
    };
    std::cout << dijkstra(1) << std::endl;
    return 0;
}

最短路计数

洛谷P1144

#include <bits/stdc++.h>
#define IOS                           /
    std::ios::sync_with_stdio(false); /
    std::cin.tie(0);                  /
    std::cout.tie(0);
const int P = 100003;

int main()
{
    IOS;
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> g(n + 1);
    for (int i = 1, u, v; i <= m; ++i)
    {
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto bfs = [&](int s)
    {
        std::vector<int> dis(n + 1), cnt(n + 1), vis(n + 1);
        cnt[s] = vis[s] = 1;
        std::queue<int> q;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto v : g[u])
            {
                if (!vis[v])
                {
                    vis[v] = 1;
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
                if (dis[v] == dis[u] + 1)
                {
                    cnt[v] = (cnt[v] + cnt[u]) % P;
                }
            }
        }
        return cnt;
    };
    std::vector<int> ans = bfs(1);
    for (int i = 1; i <= n; ++i)
        std::cout << ans[i] << std::endl;
    return 0;
}

次短路计数

CF1650G

通过两次 /(bfs/) 分别计算出从 /(s/) 和 /(t/) 出发到各顶点的最短路长度与数量。然后我们可以枚举所有的边 /((u,v)/) 。如果下列两个条件均成立：

  • 顶点 /(u/) 和 /(v/) 应该包括在同一层次（与 /(s/) 的距离相同）

  • /(dis(s,u)+dis(v,t)=dis(s,t)/)

那么我们就可以建立从 /(s/) 到 /(t/) ，长度等于 /(dis(s,t) + 1/) 的次短路 /(s→…→u→v→…→t/) ，再利用乘法原理即可求出对答案的总贡献。

上述第一个条件是用于去重的，在此给出粗略证明：我们考虑从 /(s/) 走到 /(t/) ，那么每经过一条边，要么与 /(s/) 的距离变化 1 ，要么不变。考虑是次短路，所以一定存在经过某一条边时，与 /(s/) 的距离不变。这样的边具有唯一性，所以我们只需枚举并找出所有满足这些条件的边，判断其路径长度是否满足条件即可。

#include <bits/stdc++.h>
#define PII std::pair<int, int>
#define w first
#define c second
using ll = long long;
const int P = 1e9 + 7;

char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

ll solve()
{
    int n = read(), m = read(), s = read(), t = read();
    std::vector<std::vector<int>> g(n + 1);
    std::vector<PII> e;
    for (int i = 1, u, v; i <= m; ++i)
    {
        u = read(), v = read();
        g[u].push_back(v), g[v].push_back(u);
        e.push_back({u, v});
    }
    auto bfs = [&](int st)
    {
        std::vector<PII> dis(n + 1);
        std::vector<bool> vis(n + 1);
        std::queue<int> q;
        q.push(st);
        dis[st] = {0, 1}, vis[st] = true;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto v : g[u])
            {
                if (!vis[v])
                {
                    dis[v].w = dis[u].w + 1;
                    vis[v] = true;
                    q.push(v);
                }
                if (dis[v].w == dis[u].w + 1)
                {
                    dis[v].c = (dis[v].c + dis[u].c) % P;
                }
            }
        }
        return dis;
    };
    std::vector<PII> ds = bfs(s), dt = bfs(t);
    ll ans = ds[t].c;
    for (auto [u, v] : e)
    {
        if (ds[u].w ^ ds[v].w)
            continue;
        if (ds[u].w + dt[v].w == ds[t].w)
            ans = (ans + 1ll * ds[u].c * dt[v].c % P) % P;
        if (ds[v].w + dt[u].w == ds[t].w)
            ans = (ans + 1ll * ds[v].c * dt[u].c % P) % P;
    }
    return ans;
}

int main(int argc, char const *argv[])
{
    int t = read();
    while (t--)
        printf("%lld/n", solve());
    return 0;
}

多源多汇最短路

模型一： /(n/) 个点， /(m/) 条双向边，现有 /(p/) 个特殊点，求从任意一个点出发，到附近最近特殊点的最短距离。

解法：一般这种题型的 /(n,m/) 均大于 /(Floyd/) 的承受范围，因此不妨转换思路，建立一个虚拟节点 /(s/)，然后 /(s/) 向每个特殊点（或是起点）都连一条距离为 /(0/) 的边，再以 /(s/) 为起点跑 /(Dijkstra/) 求出 /(s/) 到各点的最短路，即可得任意一点到附近最近特殊点的最短路。

模型二：给你一张有向图，存在多个起点，多个终点，可以从任一起点出发，求到达任一终点的最短距离。

解法：同理，建立一个超级源点 /(s/)，然后 /(s/) 向每个起点都连一条距离为 /(0/) 的边，建立一个超级汇点 /(t/)，然后每个终点都向 /(t/) 连一条距离为 /(0/) 的边，之后跑 /(Dijkstra/) 即可。

G – Foreign Friends

#include <bits/stdc++.h>
#define IOS                           /
    std::ios::sync_with_stdio(false); /
    std::cin.tie(0);                  /
    std::cout.tie(0);
#define PII std::pair<int, int>
using ll = long long;
const ll inf = 1e18;

struct node
{
    ll dist;
    int id, city;
    friend bool operator<(const node lft, const node rht) { return lft.dist > rht.dist; };
};

int main()
{
    IOS;
    int n, m, k, l;
    std::cin >> n >> m >> k >> l;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    std::vector<int> p;
    for (int i = 1, x; i <= l; ++i)
    {
        std::cin >> x;
        p.push_back(x);
    }
    std::vector<std::vector<PII>> g(n + 1);
    for (int i = 1, x, y, z; i <= m; ++i)
    {
        std::cin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    std::vector<ll> ans(n + 1, inf);
    auto dijkstra = [&]()
    {
        std::vector<int> vis(n + 1), upd(n + 1);
        std::priority_queue<node> q;
        for (auto x : p)
            q.push({0, x, a[x]});
        while (!q.empty())
        {
            node now = q.top();
            q.pop();
            int u = now.id;
            if (vis[u] > 1 || upd[u] == now.city)
                continue;
            if (a[u] != now.city)
                ans[u] = std::min(ans[u], now.dist);
            ++vis[u], upd[u] = now.city;
            for (auto [v, w] : g[u])
                q.push({now.dist + w, v, now.city});
        }
        return ans;
    };
    dijkstra();
    for (int i = 1; i <= n; ++i)
        std::cout << (ans[i] == inf ? -1 : ans[i]) << " ";
    return 0;
}

传递闭包

离散数学上的东西，可以通过 /(Floyd/) 求出。

#include <bits/stdc++.h>

int main(int argc, char const *argv[])
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> f(n + 1, std::vector<int>(n + 1));
    for (int i = 1; i <= n; ++i)
        f[i][i] = 1;
    for (int i = 1, u, v; i <= m; ++i)
    {
        std::cin >> u >> v;
        f[u][v] = f[v][u] = 1;
    }
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                f[i][j] |= f[i][k] & f[k][j];
    return 0;
}

Sosing It All Out

#include <bits/stdc++.h>
#define IOS                           /
    std::ios::sync_with_stdio(false); /
    std::cin.tie(0);                  /
    std::cout.tie(0);
#define id(x) (x - 'A' + 1)

int main()
{
    IOS;
    int n, m;
    std::string s;
    auto flody = [&](std::vector<std::vector<int>> &g)
    {
        std::vector<std::vector<int>> f(n + 1, std::vector<int>(n + 1));
        f = g;
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                {
                    f[i][j] |= f[i][k] & f[k][j];
                    if (i != j && f[i][j] && f[j][i])
                        return -1;
                }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (i != j && !f[i][j] && !f[j][i])
                    return 0;
        return 1;
    };
    while (std::cin >> n >> m && n && m)
    {
        bool flag = true;
        std::vector<std::vector<int>> g(n + 1, std::vector<int>(n + 1));
        for (int i = 1; i <= m; ++i)
        {
            std::cin >> s;
            int u = id(s[0]), v = id(s[2]);
            g[u][v] = 1;
            if (flag)
            {
                int now = flody(g);
                if (u == v)
                    now = -1;
                if (now == -1)
                {
                    flag = false;
                    std::cout << "Inconsistency found after " << i << " relations." << std::endl;
                }
                else if (now == 1)
                {
                    flag = false;
                    std::cout << "Sosed sequence determined after " << i << " relations: ";
                    for (int k = 1; k <= n; ++k)
                        for (int i = 1; i <= n; ++i)
                            for (int j = 1; j <= n; ++j)
                                g[i][j] |= g[i][k] & g[k][j];
                    std::vector<int> ans(n + 1);
                    for (int i = 1; i <= n; ++i)
                    {
                        int cnt = 0;
                        for (int j = 1; j <= n; ++j)
                            if (i != j && g[j][i])
                                ++cnt;
                        ans[cnt + 1] = i;
                    }
                    for (int i = 1; i <= n; ++i)
                        std::cout << (char)(ans[i] + 'A' - 1);
                    std::cout << "." << std::endl;
                }
            }
        }
        if (flag)
            std::cout << "Sosed sequence cannot be determined." << std::endl;
    }
    return 0;
}

最小环

最短路小结

Sightseeing trip

#include <bits/stdc++.h>
#define IOS                           /
    std::ios::sync_with_stdio(false); /
    std::cin.tie(0);                  /
    std::cout.tie(0);
using ll = long long;
const ll inf = 0x3f3f3f3f;

int main()
{
    IOS;
    int n, m;
    ll ans = inf;
    std::cin >> n >> m;
    std::vector<std::vector<ll>> f, g;
    f = g = std::vector<std::vector<ll>>(n + 1, std::vector<ll>(n + 1, inf));
    for (int i = 1; i <= n; ++i)
        g[i][i] = 0;
    for (int i = 1, x, y, z; i <= m; ++i)
    {
        std::cin >> x >> y >> z;
        g[x][y] = g[y][x] = std::min(g[x][y], 1ll * z);
    }
    f = g;
    std::vector<int> path; //具体方案
    std::vector<std::vector<int>> pos(n + 1, std::vector<int>(n + 1));
    std::function<void(int, int)> getPath = [&](int x, int y)
    {
        if (!pos[x][y])
            return;
        getPath(x, pos[x][y]);
        path.push_back(pos[x][y]);
        getPath(pos[x][y], y);
    };
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i < k; ++i)
            for (int j = i + 1; j < k; ++j)
                if (ans > f[i][j] + g[i][k] + g[k][j])
                {
                    ans = f[i][j] + g[i][k] + g[k][j];
                    path.clear();
                    path.push_back(k);
                    path.push_back(i);
                    getPath(i, j);
                    path.push_back(j);
                }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (f[i][j] > f[i][k] + f[k][j])
                    f[i][j] = f[i][k] + f[k][j], pos[i][j] = k;
    }
    if (ans == inf)
        std::cout << "No solution.";
    else
        for (auto x : path)
            std::cout << x << " ";
    std::cout << std::endl;
    return 0;
}

F. Find the Length

题意：对于给定带权无向图的每个顶点，计算包含该顶点的最小环长度。

思路：以每个点为源点 /(s/) 跑 /(Dijkstra/) 算法，得到一棵以其为根的最短路树。用 HLD 为 LCA 查询预处理该树。

考虑不在最短路树上的边 /(e = /{ u, v /}/) 。如果 /(LCA(u, v) = s/) ，那么该路径是一个包含当前根节点的简单环，其权重为 /(dis[u] + dis[v] + w(e)/) 。顶点 /(s/) 的答案即是所有这类环的最小值。

#include <bits/stdc++.h>
#define IOS                           /
    std::ios::sync_with_stdio(false); /
    std::cin.tie(0);                  /
    std::cout.tie(0);
#define PLL std::pair<ll, ll>
using ll = long long;
const ll inf = 1e18;

struct HLD
{
    int N;
    std::vector<std::vector<int>> &G;
    std::vector<int> fa, siz, dep, son, top;
    HLD(std::vector<std::vector<int>> &G, int root = 0) : N(G.size()), G(G), fa(N, 0), siz(N, 0), dep(N, 0), son(N, 0), top(N, 0)
    {
        dfs1(root, 0);
        dfs2(root, root);
    };
    void dfs1(int u, int f)
    {
        siz[u] = 1, fa[u] = f, dep[u] = dep[f] + 1;
        for (auto v : G[u])
            if (v != f)
            {
                dfs1(v, u);
                siz[u] += siz[v];
                if (siz[v] > siz[son[u]])
                    son[u] = v;
            }
    }
    void dfs2(int u, int t)
    {
        top[u] = t;
        if (son[u])
            dfs2(son[u], t);
        for (auto v : G[u])
            if (v != fa[u] && v != son[u])
                dfs2(v, v);
    }
    int lca(int x, int y)
    {
        while (top[x] ^ top[y])
        {
            if (dep[top[x]] < dep[top[y]])
                std::swap(x, y);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y])
            std::swap(x, y);
        return x;
    }
};

int main()
{
    IOS;
    int n;
    std::cin >> n;
    std::vector<std::vector<PLL>> g(n + 1);
    for (int i = 1, w; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            std::cin >> w;
            if (w > 0)
                g[i].push_back({j, w});
        }
    }
    std::vector<ll> ans(n + 1, -1ll);
    for (int s = 1; s <= n; ++s)
    {
        std::vector<bool> vis(n + 1);
        std::vector<int> fa(n + 1);
        std::vector<ll> dis(n + 1, inf);
        std::priority_queue<PLL, std::vector<PLL>, std::greater<PLL>> pq;
        dis[s] = 0;
        pq.push({0, s});
        while (!pq.empty())
        {
            int u = pq.top().second;
            pq.pop();
            if (vis[u])
                continue;
            vis[u] = true;
            for (auto [v, w] : g[u])
            {
                if (dis[v] > dis[u] + w)
                {
                    fa[v] = u;
                    dis[v] = dis[u] + w;
                    pq.push({dis[v], v});
                }
            }
        }
        std::vector<std::vector<int>> G(n + 1);
        for (int i = 1; i <= n; ++i)
            if (fa[i])
                G[fa[i]].push_back(i);
        HLD hld(G, s);
        for (auto [v, w] : g[s])
        {
            if (fa[v] == s)
                continue;
            if (ans[s] == -1ll || ans[s] > dis[v] + w)
                ans[s] = dis[v] + w;
        }
        for (int u = 1; u <= n; ++u)
        {
            if (u == s)
                continue;
            if (dis[u] == inf)
                continue;
            for (auto [v, w] : g[u])
            {
                if (v == s)
                    continue;
                if (hld.lca(u, v) != s)
                    continue;
                if (ans[s] == -1ll || ans[s] > dis[u] + dis[v] + w)
                    ans[s] = dis[u] + dis[v] + w;
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        std::cout << ans[i] << std::endl;
    return 0;
}

原创文章，作者：306829225，如若转载，请注明出处：https://blog.ytso.com/244477.html

赞 (0)
0
上一篇 2022年4月17日
下一篇 2022年4月17日

相关推荐

发表回复

登录后才能评论