分层图解决的一些最短路问题

关于分层图

340. 通信线路 - AcWing题库

在郊区有 NN 座通信基站，PP 条 双向 电缆，第 ii 条电缆连接基站 AiAi 和 BiBi。

特别地，11 号基站是通信公司的总站，NN 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 ii 条电缆需要花费 LiLi。

电话公司正在举行优惠活动。

农产主可以指定一条从 11 号基站到 NN 号基站的路径，并指定路径上不超过 KK 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式

第 11 行：三个整数 N，P，KN，P，K。

第 2..P+12..P+1 行：第 i+1i+1 行包含三个整数 Ai,Bi,LiAi,Bi,Li。

输出格式

包含一个整数表示最少花费。

若 11 号基站与 NN 号基站之间不存在路径，则输出 −1−1。

数据范围

0≤K<N≤10000≤K<N≤1000,
1≤P≤100001≤P≤10000,
1≤Li≤10000001≤Li≤1000000

输入样例：

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例：

4

解法一：

由于选择k条边免费，所以建立k层分层图，每条边与他同层临点建边不会改变他的连通性，k条免费的边就相当于每层之间的边的边权为0，在k层之间跑最短路就相应的对应上原题意

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x);
#define X first
#define Y second
#define int long long
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e6 + 10, M = 2e7 + 10, INF = 0x3f3f3f3f, EPS = 1e-8;
typedef pair<int, int> PII;
int n, p, k;
int h[N], e[N], w[N], ne[N], idx;
int d[N];
bool st[N];
void add(int a, int b, int c) // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra()
{
    mst(d, 0x3f);
    d[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

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

        int id = t.Y, dist = t.X;
        if (st[id])
            continue;
        st[id] = true;

        for (int i = h[id]; ~i; i = ne[i])
        {
            int j = e[i], v = max(w[i], d[id]);
            if (d[j] > v)
            {
                d[j] = v;
                heap.push({d[j], j});
            }
        }
    }
}
signed main()
{
    FAST;
    mst(h, -1);
    
    cin >> n >> p >> k;
    for (int i = 1; i <= p; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);

        for (int j = 0; j < k; j++)
        {
            add(a + j * n, b + (j + 1) * n, 0);
            add(b + j * n, a + (j + 1) * n, 0);

            add(a + (j + 1) * n, b + (j + 1) * n, c);
            add(b + (j + 1) * n, a + (j + 1) * n, c);
        }
    }

    for (int i = 1; i <= k; i++)
    {
        add(i * n, (i + 1) * n, 0);
    }

    dijkstra();

    if (d[n * (k + 1)] >= 1e6+10)
        cout << "-1" << endl;
    else
        cout << d[n * (k + 1)] << endl;
    return 0;
}

 解法二：

340. 通信线路 - AcWing题库

---

I-旅行_2022河南萌新联赛第（三）场：河南大学 (nowcoder.com)

 

 根据题意：每个邻点之间建立需要核酸与不需要核酸的两种情况的两种边，最后只会有两种情况（上一个点到n号点需要核酸，边权为w，or上一个点到n号点不需要核酸，边权为ｗ＋ｘ）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x);
#define X first
#define Y second
#define int long long
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, M = 4 * N, INF = 0x3f3f3f3f, EPS = 1e-8;
typedef pair<int, int> PII;
int n, m, x;
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];
void add(int a, int b, int c) // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra()
{
    mst(d, 0x3f);
    d[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

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

        int id = t.Y, dist = t.X;
        if (st[id])
            continue;
        st[id] = true;

        for (int i = h[id]; ~i; i = ne[i])
        {
            int j = e[i];
            if (d[j] > d[id] + w[i])
            {
                d[j] = d[id] + w[i];
                heap.push({d[j], j});
            }
        }
    }
}
signed main()
{
    FAST;
    mst(h, -1);

    cin >> n >> m >> x;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b + n, c + x), add(a + n, b, c);
        add(b, a + n, c + x), add(b + n, a, c);
    }

    dijkstra();

    cout << min(d[n], d[2 * n]) << endl; // d[n]代表最后到达n号点是需要核酸， d[2*n]代表最后到达n号点不需要核酸

    return 0;
}

---

2953. 飞行路线 - AcWing题库

 同理与上题类似，建立ｋ层分层图相当于ｋ－１层之间边权都为０

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x);
#define X first
#define Y second
#define int long long
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2e5+10, M = 5e6+10, INF = 0x3f3f3f3f, EPS = 1e-8;
typedef pair<int, int> PII;
int n, m, k;
int s, t;
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];
void add(int a, int b, int c) // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra()
{
    mst(d, 0x3f);
    d[s] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});

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

        int id = t.Y, dist = t.X;
        if (st[id])
            continue;
        st[id] = true;

        for (int i = h[id]; ~i; i = ne[i])
        {
            int j = e[i];
            if (d[j] > d[id] + w[i])
            {
                d[j] = d[id] + w[i];
                heap.push({d[j], j});
            }
        }
    }
}

signed main()
{
    FAST;
    cin >> n >> m >> k;
    cin >> s >> t;
    mst(h, -1);

    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);

        for (int j = 1; j <= k; j++)
        {
            add(a + j * n, b + j * n, c);
            add(b + j * n, a + j * n, c);
            add(a + (j - 1) * n, b + j * n, 0);
            add(b + (j - 1) * n, a + j * n, 0);
        }
    }

    for (int i = 1; i <= k; i++)
    {
        add(t + (i - 1) * n, t + i * n, 0);
    }

    dijkstra();

    cout << d[n * k + t] << endl;

    return 0;
}

---

341. 最优贸易 - AcWing题库

 建三层图，第二层代表买，第三层代表卖；

同层之间不进行买卖，边权都为0；

相邻层的相同点连通表示买卖的权值，买为负权，卖为正权，第一层与第二层之间为负权边，第二层与都三层之间为正权边；

最后SPFA跑一遍最长路，(可以将第一层与第二层建正权，第二层与第三层建负权，跑最短路，-d[3*n]是答案),d[3*n]即为答案；

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x);
#define X first
#define Y second
#define int long long
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200010, M = 4 * N, INF = 0x3f3f3f3f, EPS = 1e-8;
typedef pair<int, int> PII;
int n, m;
int val[N];
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];
void add(int a, int b, int c) // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void SPFA() // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{
    memset(d, -INF, sizeof d);
    d[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;

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

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] < d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}
signed main()
{
    FAST;
    mst(h, -1);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (c == 1)
        {
            add(a, b, 0);
            add(a + n, b + n, 0);
            add(a + 2 * n, b + 2 * n, 0);
        }
        else if (c == 2)
        {
            add(a, b, 0), add(b, a, 0);
            add(a + n, b + n, 0), add(b + n, a + n, 0);
            add(a + 2 * n, b + 2 * n, 0), add(b + 2 * n, a + 2 * n, 0);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        add(i, i + n, -val[i]);
        add(i + n, i + 2 * n, val[i]);
    }

    SPFA();

    if (d[3 * n] >= 0)
        cout << d[3 * n] << endl;
    else
        cout << "0" << endl;

    return 0;
}