Extension of graph theory

Super source

Choose the best route

This topic is the template question

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 20010, INF = 0x3f3f3f3f;

int n, m, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];
bool st[N];

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

void spfa()
{
    
    int scnt;
    scanf("%d", &scnt);

    memset(dist, 0x3f, sizeof dist);

    int hh = 0, tt = 0;
    while (scnt -- )
    {
    
        int u;
        scanf("%d", &u);
        dist[u] = 0;
        q[tt ++ ] = u;
        st[u] = true;
    }

    while (hh != tt)
    {
    
        int t = q[hh ++ ];
        if (hh == N) hh = 0;

        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
    
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
    
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
    
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

int main()
{
    
    while (scanf("%d%d%d", &n, &m, &T) != -1)
    {
    
        memset(h, -1, sizeof h);
        idx = 0;

        while (m -- )
        {
    
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }

        spfa();

        if (dist[T] == INF) dist[T] = -1;
        printf("%d\n", dist[T]);
    }

    return 0;
}

Demolition point （ Hierarchical graph ）

Saving Private Ryan

state It's like pressing that feeling

In fact, the disassembly point is an additional one-dimensional state , Added some restrictions
In the shortest circuit , All problems that need to be broken down or layered , You can use it first dp To consider , The other way is , Consider the current state , Which statuses can be updated .

All the problems in the shortest circuit , The second one is more intuitive , Because the second is closer to the shortest path model
That is, consider which states can be updated by the current state

One more key is sure to pay off , So if you have a key, use it

dp There are two ways to calculate the state in , The first is to calculate the current state , Which states can be changed

Although it works dp Think about it , But it doesn't work dp Do it with your mind , because dp You need a topological order , But there may be rings in this topic

dp It can be regarded as the shortest path on the topology

In this way, it can be seen that there are only 0 and 1 Two kinds of weights , Then you can search widely with double ended queues

When running the shortest way , For convenience , A two-dimensional coordinate can be mapped into a one-dimensional , Pictured

#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
#include <set>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 11, M = 360, P = 1 << 10;

int n, m, k, p;
int h[N * N], e[M], w[M], ne[M], idx;
int g[N][N], key[N * N];// Number the points , Record where the key is located 
int dist[N * N][P];// Record the minimum number of steps used in this state of this point 
bool st[N * N][P];// Judge whether this state of this point has been used 

set<PII> edges;

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

void build()
{
    
    int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int u = 0; u < 4; u ++ )
            {
    
                int x = i + dx[u], y = j + dy[u];
                if (!x || x > n || !y || y > m) continue;
                int a = g[i][j], b = g[x][y];
                if (!edges.count({
    a, b})) add(a, b, 0);// No doors and walls , There is a two-way side 
            }
}

int bfs()
{
    
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;

    deque<PII> q;
    q.push_back({
    1, 0});

    while (q.size())
    {
    
        PII t = q.front();
        q.pop_front();

        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;

        if (t.x == n * m) return dist[t.x][t.y];

        if (key[t.x])
        {
    
            int state = t.y | key[t.x];
            if (dist[t.x][state] > dist[t.x][t.y])
            {
    
                dist[t.x][state] = dist[t.x][t.y];
                q.push_front({
    t.x, state});
            }
        }

        for (int i = h[t.x]; ~i; i = ne[i])
        {
    
            int j = e[i];
            if (w[i] && !(t.y >> w[i] - 1 & 1)) continue;   //  There is a door and no key 
            if (dist[j][t.y] > dist[t.x][t.y] + 1)
            {
    
                dist[j][t.y] = dist[t.x][t.y] + 1;
                q.push_back({
    j, t.y});
            }
        }
    }

    return -1;
}

int main()
{
    
    cin >> n >> m >> p >> k;

    for (int i = 1, t = 1; i <= n; i ++ )// Initialize node number 
        for (int j = 1; j <= m; j ++ )
            g[i][j] = t ++ ;

    memset(h, -1, sizeof h);
    while (k -- )
    {
    
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        int a = g[x1][y1], b = g[x2][y2];// Find the number corresponding to two points 

        edges.insert({
    a, b}), edges.insert({
    b, a});// It means there is a wall or door here 
        if (c) add(a, b, c), add(b, a, c);// Building a door , The wall cannot be passed , So just mark , Do not build edges 
    }

    build();// Establish the remaining edges 

    int s;
    cin >> s;
    while (s -- )
    {
    
        int x, y, c;
        cin >> x >> y >> c;
        key[g[x][y]] |= 1 << c - 1;// Record key 
    }

    cout << bfs() << endl;

    return 0;
}

Use dp Thought counting class of

Shortest circuit count

dp It can be roughly regarded as the shortest path running on the topology

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 400010, mod = 100003;

int n, m;
int h[N], e[M], ne[M], idx;
int dist[N], cnt[N];
int q[N];

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

void bfs()
{
    
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    cnt[1] = 1;

    int hh = 0, tt = 0;
    q[0] = 1;

    while (hh <= tt)
    {
    
        int t = q[hh ++ ];

        for (int i = h[t]; ~i; i = ne[i])
        {
    
            int j = e[i];
            if (dist[j] > dist[t] + 1)
            {
    
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t];
                q[ ++ tt] = j;
            }
            else if (dist[j] == dist[t] + 1)// It can be seen here as a state transition equation 
            {
    
                cnt[j] = (cnt[j] + cnt[t]) % mod;
            }
        }
    }
}

int main()
{
    
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    while (m -- )
    {
    
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    bfs();

    for (int i = 1; i <= n; i ++ ) printf("%d\n", cnt[i]);

    return 0;
}

Sightseeing

The meaning of this topic is probably , Give you the starting point and the ending point , Ask you how many shortest paths there are at most , If the secondary short circuit is more than the shortest one 1, Then add the number of short circuits last time

Open one-dimensional storage times more short circuit , And then like dp Same as dij Update inside

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010, M = 20010;

struct Ver
{
    
    int id, type, dist;
    bool operator> (const Ver &W) const
    {
    
        return dist > W.dist;
    }
};

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2], cnt[N][2];
bool st[N][2];

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

int dijkstra()
{
    
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);

    dist[S][0] = 0, cnt[S][0] = 1;
    priority_queue<Ver, vector<Ver>, greater<Ver>> heap;
    heap.push({
    S, 0, 0});

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

        int ver = t.id, type = t.type, distance = t.dist, count = cnt[ver][type];
        if (st[ver][type]) continue;
        st[ver][type] = true;

        for (int i = h[ver]; ~i; i = ne[i])
        {
    
            int j = e[i];
            if (dist[j][0] > distance + w[i])
            {
    
                dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0];
                heap.push({
    j, 1, dist[j][1]});
                dist[j][0] = distance + w[i], cnt[j][0] = count;
                heap.push({
    j, 0, dist[j][0]});
            }
            else if (dist[j][0] == distance + w[i]) cnt[j][0] += count;
            else if (dist[j][1] > distance + w[i])
            {
    
                dist[j][1] = distance + w[i], cnt[j][1] = count;
                heap.push({
    j, 1, dist[j][1]});
            }
            else if (dist[j][1] == distance + w[i]) cnt[j][1] += count;
        }
    }

    int res = cnt[T][0];
    if (dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];

    return res;
}

int main()
{
    
    int cases;
    scanf("%d", &cases);
    while (cases -- )
    {
    
        scanf("%d%d", &n, &m);
        memset(h, -1, sizeof h);
        idx = 0;

        while (m -- )
        {
    
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d%d", &S, &T);

        printf("%d\n", dijkstra());
    }

    return 0;
}