dp是特殊的最短路，是無環(huán)圖（拓?fù)鋱D）上的最短路問題

1137. 選擇最佳線路

1137. 選擇最佳線路 - AcWing題庫(kù)

// 反向建圖就行
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;
const int N = 1e3 + 10, M = 2e4 + 10;
int h[N], e[M], ne[M], w[M], idx;
int n, m, s;
int a[N];
int dis[N]; bool st[N];

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(st, 0, sizeof(st));
    dis[s] = 0;
    q.push({ dis[s], s });
    while (q.size())
    {
        auto t = q.top(); q.pop();
        int x = t.second, d = t.first;
        if (st[x]) continue;
        st[x] = true;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (dis[y] > d + w[i]) 
            {
                dis[y] = d + w[i];
                q.push({ dis[y], y });
            }
        }
    }
}

int main()
{
    while (~scanf("%d%d%d", &n, &m, &s))
    {
        idx = 0;
        memset(h, -1, sizeof(h));
        int x, y, d;
        while ( m -- )
        {
            scanf("%d%d%d", &x, &y, &d);
            add(y, x, d);
        }
        
        int wn;
        scanf("%d", &wn);
        for (int i = 1; i <= wn; ++ i ) scanf("%d", &a[i]);
        
        dijkstra();
        int res = 0x3f3f3f3f;
        for (int i = 1; i <= wn; ++ i ) res = min(res, dis[a[i]]);
        
        if (res == 0x3f3f3f3f) puts("-1");
        else printf("%d\n", res);
    }
    return 0;
}

對(duì)于每組測(cè)試數(shù)據(jù)，該重置的數(shù)據(jù)要重置，我沒有重置idx，導(dǎo)致TLE

處理反向建圖，還有一種擴(kuò)展做法：虛擬源點(diǎn)

設(shè)置虛擬源點(diǎn)，與每個(gè)起點(diǎn)之間連接邊權(quán)為0的邊
原問題：從多個(gè)源點(diǎn)出發(fā)，到達(dá)終點(diǎn)的最短路徑
先問題：從虛擬源點(diǎn)出發(fā)，到達(dá)終點(diǎn)的最短路徑
兩者的最短路徑一一對(duì)應(yīng)，并且路徑和相同

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;
const int N = 1e3 + 10, M = 3e4 + 10;
int h[N], e[M], ne[M], w[M], idx;
int n, m, s;
int a[N];
int dis[N]; bool st[N];

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(st, 0, sizeof(st));
    dis[0] = 0;
    q.push({ dis[0], 0 });
    while (q.size())
    {
        auto t = q.top(); q.pop();
        int x = t.second, d = t.first;
        if (st[x]) continue;
        st[x] = true;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (dis[y] > d + w[i]) 
            {
                dis[y] = d + w[i];
                q.push({ dis[y], y });
            }
        }
    }
}

int main()
{
    while (~scanf("%d%d%d", &n, &m, &s))
    {
        idx = 0;
        memset(h, -1, sizeof(h));
        int x, y, d;
        while ( m -- )
        {
            scanf("%d%d%d", &x, &y, &d);
            add(x, y, d);
        }
        
        int wn;
        scanf("%d", &wn);
        for (int i = 1; i <= wn; ++ i ) 
        {
            scanf("%d", &a[i]);
            add(0, a[i], 0);  // 設(shè)置虛擬源點(diǎn)
        }
        
        dijkstra();

        if (dis[s] == 0x3f3f3f3f) puts("-1");
        else printf("%d\n", dis[s]);
    }
    return 0;
}

debug：將虛擬源點(diǎn)與起點(diǎn)之間建立邊，要注意M的大小是否足夠，又是M開小了…

1131. 拯救大兵瑞恩

1131. 拯救大兵瑞恩 - AcWing題庫(kù)

從集合的角度分析
狀態(tài)表示：
集合：起點(diǎn)為左上角，終點(diǎn)為圖中任意一點(diǎn)的所有路徑，用$f(x,y)$表示終點(diǎn)為$[x,y]$的路徑
屬性：最小時(shí)間（路徑和）
所以$f(x,y)$表示終點(diǎn)為$[x,y]$的最小路徑和
但是圖中存在無法通過的墻以及需要鑰匙打開的門，所以用兩個(gè)維度表示路徑將無法更新集合
考慮增加一個(gè)維度$state$，狀態(tài)壓縮，表示擁有的鑰匙狀態(tài)
即$f(x,y,state)$表示擁有鑰匙的狀態(tài)為$state$時(shí)，遞達(dá)$[x,y]$的最短路

狀態(tài)計(jì)算：
如何劃分$f(x,y,state)$？一般的dp問題是從后往前考慮，圖論中的集合分析一般從前往后考慮
即$f(x,y,state)$能推導(dǎo)出哪些集合？
若$[x,y]$有鑰匙，可以撿起這些鑰匙，假設(shè)鑰匙的狀態(tài)為key，那么狀態(tài)推導(dǎo)就是$f(x,y,state)?>f(x,y,state|key)$
若$[x,y]$無鑰匙，那么可以向相鄰的位置走，$f(x,y,state)?>f(nx,ny,state)$，此時(shí)的最短距離要+1
由于這個(gè)問題中存在環(huán)路，所以無法用dp更新集合，只能用最短路算法更新集合

這題比較麻煩的是：建邊，相鄰兩個(gè)位置若沒有墻，那么可以建立一條權(quán)值為1的邊
如何表示兩個(gè)二維坐標(biāo)之間有邊？這里涉及到二維坐標(biāo)到一維的轉(zhuǎn)換，然后用鄰接表存儲(chǔ)圖
若兩個(gè)位置之間存在門，用邊權(quán)表示門的種類，但是實(shí)際的邊權(quán)為1
若兩個(gè)位置之間既不存在門，也不存在墻，那么創(chuàng)建一條權(quán)值為0的邊，但時(shí)間的邊權(quán)為1。所以$w[i]$為非0表示這個(gè)邊上有道門，為0表示可以直接通過
對(duì)于墻的情況，直接忽略，不建立邊（表示不連通）即可
用set存儲(chǔ)已經(jīng)建立的邊，防止重復(fù)建邊

#include <iostream>
#include <cstring>
#include <deque>
#include <set>
using namespace std;

typedef pair<int, int> PII;
const int N = 11, P = 1 << N;
const int M = 400;
int h[N * N], e[M], ne[M], w[M], idx;
int g[N][N]; // 二維到一維的轉(zhuǎn)換
int key[N * N]; // 每個(gè)坐標(biāo)的鑰匙狀態(tài)
int dis[N * N][P]; bool st[N * N][P];
set<PII> s;

int n, m, p, k;

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void build()
{
    int dx[4] = { 0, 1, 0, -1}, dy[4] = { 1, 0, -1, 0 };
    for (int x = 1; x <= n; ++ x )
        for (int y = 1; y <= m; ++ y )
            for (int i = 0; i < 4; ++ i )
            {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx > 0 && nx <= n && ny > 0 && ny <= m)
                {
                    int a = g[x][y], b = g[nx][ny];
                    if (!s.count({a, b})) add(a, b, 0);
                }
            }
}

int bfs()
{
    memset(dis, 0x3f, sizeof(dis));
    deque<PII> q;
    dis[1][0] = 0;
    q.push_back({1, 0});
    while (q.size())
    {
        auto t = q.front(); q.pop_front();
        int x = t.first, state = t.second;
        if (st[x][state]) continue;
        st[x][state] = true;
        
        if (x == n * m) return dis[n * m][state];
        if (key[x])
        {
            int nstate = state | key[x];
            if (dis[x][nstate] > dis[x][state])
            {
                dis[x][nstate] = dis[x][state];
                q.push_front({x, nstate});
            }
        }
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (w[i] && !((state >> w[i]) & 1)) continue;
            if (dis[y][state] > dis[x][state] + 1)
            {
                dis[y][state] = dis[x][state] + 1;
                q.push_back({y, state});
            }
        }
    }   
    return -1;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d%d%d", &n, &m, &p, &k);
    
    int cnt = 1;
    for (int i = 1; i <= n; ++ i )
        for (int j = 1; j <= m; ++ j ) 
            g[i][j] = cnt ++ ;
    
    int x1, y1, x2, y2, x, y, d;
    while ( k -- )
    {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &d);
        x = g[x1][y1], y = g[x2][y2];
        s.insert({x, y}), s.insert({y, x});
        
        if (d) add(x, y, d), add(y, x, d);
    }
    
    build(); // 建立除了門和墻的邊
    
    int l;
    scanf("%d", &l);
    while ( l -- )
    {
        scanf("%d%d%d", &x, &y, &d);
        key[g[x][y]] |= 1 << d;
    }
    
    printf("%d\n", bfs());
    
    return 0;
}

debug：int x = t.first, state = t.second寫成int x = t.secnd, state = t.first
只能說是dijkstra寫多了

1134. 最短路計(jì)數(shù)

1134. 最短路計(jì)數(shù) - AcWing題庫(kù)

從集合的角度考慮，$f(i)$表示圖中第i個(gè)點(diǎn)的最短路條數(shù)，假設(shè)與i相連的點(diǎn)由k個(gè)，那么$f(i)=f(s_1)+f(s_2)+...+f(s_k)$，第i個(gè)點(diǎn)的最短路條數(shù)由與之直接相連的點(diǎn)的最短路條數(shù)累加而成
那么要求解$f(i)$，就要先算出它的子集，但是圖論問題可能存在環(huán)，無法確定$f(i)$是否會(huì)影響它的子集。所以只能在拓?fù)鋱D中才能這樣更新集合，考慮最短路算法的更新是否具有拓?fù)湫?/p>

三種求最短路的方法：1.BFS 2.Dijkstra 3.Bellman-ford
探討它們求解最短路時(shí)，是否具有拓?fù)湫颍?br> 對(duì)于BFS，由于每個(gè)點(diǎn)只會(huì)入隊(duì)一次且只會(huì)出隊(duì)一次，說明BFS的更新天然地具有拓?fù)湫?，因?yàn)槌鲫?duì)的點(diǎn)不會(huì)被后續(xù)入隊(duì)的點(diǎn)影響
對(duì)于Dijkstra，由于每個(gè)點(diǎn)會(huì)入隊(duì)多次，但只會(huì)出隊(duì)一次，也說明了Dijkstra的更新天然地具有拓?fù)湫?br> 對(duì)于spfa，由于它是暴力算法的優(yōu)化，每個(gè)點(diǎn)都會(huì)入隊(duì)與出隊(duì)多次，所以spfa的更新不具有拓?fù)湫?，已?jīng)出隊(duì)（更新完成）的點(diǎn)可能影響被后續(xù)入隊(duì)的點(diǎn)影響
即bfs和dijkstra的更新是一顆最短路樹，而spfa的更新不是一顆最短路樹

統(tǒng)計(jì)最短路條數(shù)時(shí)，可以遍歷最短路樹
若統(tǒng)計(jì)i節(jié)點(diǎn)的最短路條數(shù)，只需要累乘父節(jié)點(diǎn)的數(shù)量即可
而spfa的更新不具有拓?fù)湫?，即不存在最短路樹，要是圖中存在負(fù)權(quán)邊，無法使用天然具有拓?fù)湫虻腷fs和dijkstra時(shí)，只能先用spfa求出最短路，維護(hù)出最短路樹，再求最短路條數(shù)

一般情況下，圖中不能存在權(quán)值為0的點(diǎn)，否則無法建立出最短路樹，因?yàn)檫_(dá)到某一個(gè)點(diǎn)的最短路不能確定

這題直接用bfs更新最短路，在更新過程中完成最短路條數(shù)的統(tǒng)計(jì)：用x更新y時(shí)，dis[y] > dis[x] + 1時(shí)，y的最短路數(shù)量等于x的最短路數(shù)量
若dis[y] == dix[x] + 1，y的最短路條數(shù)等于兩者的數(shù)量累加

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = 4e5 + 10, mod = 100003;
int h[N], e[M], ne[M], idx;
int dis[N], q[N], hh, tt = -1;
int cnt[N];
int n, m;

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

void bfs()
{
    memset(dis, 0x3f, sizeof(dis));
    q[++ tt ] = 1;
    dis[1] = 0, cnt[1] = 1;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (dis[y] > dis[x] + 1)
            {
                dis[y] = dis[x] + 1;
                q[++ tt ] = y;
                cnt[y] = cnt[x];
            }
            else if(dis[y] == dis[x] + 1) cnt[y] = (cnt[y] + cnt[x]) % mod;
        }
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y;
    while ( m -- )
    {
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    
    bfs();
    
    for (int i = 1; i <= n; ++ i ) 
    {
        if (cnt[i] == 0x3f3f3f3f) puts("0");
        else printf("%d\n", cnt[i]);
    }
    return 0;
}

383. 觀光

383. 觀光 - AcWing題庫(kù)

由于無負(fù)權(quán)邊，所以用dijkstra更新最短路，同時(shí)維護(hù)最短路條數(shù)
但是題目還要維護(hù)最短路條數(shù)，所以這里用了個(gè)類似拯救大兵瑞恩的思想：狀壓
dis[i][0]表最短路距離，dis[i][1]表示次短路距離，由于次短路的更新也具有拓?fù)湫?，所以我們可以在更新次短路的時(shí)候維護(hù)次短路條數(shù)

$dis[i][1]$如何計(jì)算？與i相連的所有點(diǎn)的最短路以及次短路中，第二大的數(shù)
代碼體現(xiàn)在：
若dis[y][0] > dis[x][0] + w[i]，則更新最短路$dis[y][0]$，那么最短路成為次短路$dis[y][1]$，更新次短路，同時(shí)更新最短路
若dis[y][0] == dis[x][0] + w[i]，那么最短路條數(shù)累加，cnt[y][0] += cnt[x][0]
若dis[y][1] > dis[x][0] + w[i]，那么更新次短路$dis[y][1]$
若dis[y][1] == dis[x][0] + w[i]，那么次短路條數(shù)累加，cnt[y][1] += cnt[x][1]文章來源地址http://www.zghlxwxcb.cn/news/detail-626220.html

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1010, M = 10010;
int h[N], e[M], ne[M], w[M], idx;
int n, m, s, t;
int dis[N][2], cnt[N][2]; bool st[N][2];

struct Ver
{
    int x, d, type;
    bool operator>(const Ver& v) const // 建小堆重載>
    {
        return d > v.d;
    }
};

void add(int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

int dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));
    memset(st, 0, sizeof(st));
    memset(cnt, 0, sizeof(cnt));
    priority_queue<Ver, vector<Ver>, greater<Ver>> q;
    q.push({s, 0, 0});
    dis[s][0] = 0, cnt[s][0] = 1;
    while (q.size())
    {
        auto t = q.top(); q.pop();
        int x = t.x, d = t.d, type = t.type;
        int count = cnt[x][type];
        if (st[x][type]) continue;
        st[x][type] = true;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (dis[y][0] > d + w[i])
            {
                dis[y][1] = dis[y][0], cnt[y][1] = cnt[y][0];
                q.push({y, dis[y][1], 1});
                dis[y][0] = d + w[i], cnt[y][0] = count;
                q.push({y, dis[y][0], 0});
            }
            else if (dis[y][0] == d + w[i]) cnt[y][0] += count;
            else if(dis[y][1] > d + w[i])
            {
                dis[y][1] = d + w[i], cnt[y][1] = count;
                q.push({y, dis[y][1], 1});
            }
            else if (dis[y][1] == d + w[i]) cnt[y][1] += count;
        }
    }
    int res = cnt[t][0];
    if (dis[t][0] + 1== dis[t][1]) res += cnt[t][1];
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    while ( T -- )
    {
        idx = 0;
        memset(h, -1, sizeof(h));
        scanf("%d%d", &n, &m);
        int x, y, d;
        while ( m -- )
        {
            scanf("%d%d%d", &x, &y, &d);
            add(x, y, d);
        }
        scanf("%d%d", &s, &t);
        printf("%d\n", dijkstra());
    }
    return 0;
}

到了這里，關(guān)于第三章 圖論 No.2單源最短路之虛擬源點(diǎn)，狀壓最短路與最短路次短路條數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！