Some shortest path problems solved by hierarchical graph

About hierarchical graph

340. Communication lines - AcWing Question bank

In the suburbs  NN  A communication base station ,PP  strip   two-way   cable , The first  ii  A cable connects the base station  AiAi  and  BiBi.

Specially ,11  Base station No. 1 is the main station of the communication company ,NN  Base station is located in a farm .

Now? , The farmer wants to upgrade the communication line , Among them, upgrade the second  ii  This cable costs  LiLi.

The telephone company is holding a discount .

The farmer can designate a route from  11  Base station to  NN  The path of base station No , And specify no more than... On the path  KK  Cables , Free upgrade service provided by the telephone company .

Farmers only need to pay for the remaining cables on the path , The cost of upgrading the most expensive cable .

Ask at least how much money can be used to complete the upgrade .

Input format

The first  11  That's ok ： Three integers  N,P,KN,P,K.

The first  2..P+12..P+1  That's ok ： The first  i+1i+1  The row contains three integers  Ai,Bi,LiAi,Bi,Li.

Output format

Contains an integer indicating the least cost .

if  11  Base station No. 1 and  NN  There is no path between base stations , The output  −1−1.

Data range

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

sample input ：

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

sample output ：

4

Solution 1 ：

Because of the choice k Strip free , So build k Layer by layer diagram , Each edge is on the same level as him, and the edge construction will not change his connectivity ,k A free edge is equivalent to the edge weight of the edge between each layer is 0, stay k The shortest run between layers corresponds to the original meaning

#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) //  Add an edge a->b, The boundary right is 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;
}

  Solution 2 ：

340. Communication lines - AcWing Question bank

---

I- travel _2022 Henan Mengxin League No （ 3、 ... and ） site ： Henan University (nowcoder.com)

 

  According to the meaning ： Between each adjacent point, two sides of the two cases that need nucleic acid and do not need nucleic acid are established , In the end, there are only two situations （ Last point to n Point number needs nucleic acid , The boundary right is w,or Last point to n No nucleic acid is needed at point , The boundary right is ｗ＋ｘ）

#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) //  Add an edge a->b, The boundary right is 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] Represents the last arrival n Point No. requires nucleic acid , d[2*n] Represents the last arrival n No nucleic acid is needed at point 

    return 0;
}

---

2953. Flight path - AcWing Question bank

  Similarly, it is similar to the above question , establish ｋ The layer by layer diagram is equivalent to ｋ－１ The edge weights between layers are ０

#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) //  Add an edge a->b, The boundary right is 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. The best trade - AcWing Question bank

  Third floor plan , The second floor represents buying , The third floor represents selling ;

There is no business between the same floor , The border power is 0;

The same point connectivity of adjacent layers indicates the weight of buying and selling , Buying is negative , Sell right , Between the first layer and the second layer is the negative weight edge , Between the second floor and the third floor is the positive weight edge ;

Last SPFA Run it over The longest way ,( The first floor and the second floor can be righted , The second and third floors are built with negative rights , Run the shortest path ,-d[3*n] Yes, the answer ),d[3*n] Is the answer ;

#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) //  Add an edge a->b, The boundary right is c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void SPFA() //  seek 1 It's on the n The shortest distance of point No , If from 1 Point No. can't go to n Point number returns -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;
}