單源最短路的綜合應(yīng)用

AcWing 1135. 新年好

多次dijkstra求每個(gè)點(diǎn)到其它點(diǎn)的最短距離， 此時(shí)相當(dāng)于建好了一張圖，每個(gè)點(diǎn)之間的最短距離都知道了，接下來dfs搜一下怎么走最短即可

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 5 * 1e4 + 10, M = 2 * 1e5 + 10, INF = 0x3f3f3f3f;

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

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




void dijkstra(int start, int dist[])
{
    memset(st, 0, sizeof st);//求多次dijkstra，st每次都要初始化
    memset(dist, 0x3f, N * sizeof (int));
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    
    dist[start] = 0;//這里的dist是局部的，只不過重名了罷了，所以是一維的
        
    heap.push({dist[start], start});//PII根據(jù)第一個(gè)排序，所以dist放最前面,堆優(yōu)化版dijksra就是存PII<dist, index>的
    
    while (heap.size())
    {
        PII t = heap.top();
        heap.pop();
        int ver = t.y;
        
        if(st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}


int dfs(int u, int start, int distance)
{
    if (u == 6) return distance;//最多6層（佳佳自己的家 + 5個(gè)親戚），為什么不是7，因?yàn)榈郊鸭炎约旱募揖嚯x為0，我們不需要計(jì)算，只需要計(jì)算5層就行，不需要真正計(jì)算6層
    
    int res = INF;
    
    for (int i = 1; i <= 5; i ++ )//遍歷next是哪個(gè)站，每個(gè)i對應(yīng)一個(gè)source[i]是有實(shí)際意義的
    {
        if(!st[i])
        {
            int next = source[i];
            st[i] = true;
            res = min(res, dfs(u + 1, i, distance + dist[start][next]));//start傳i的原因是到了下一層之后起點(diǎn)就是source[i]了，只不過在本層它是next而已
            st[i] = false;//要回溯
        }
    }
    
    return res;
}


int main()
{
    memset(h, -1, sizeof h);
    
   
    cin >> n >> m;
    source[0] = 1;
    for (int i = 1; i <= 5; i ++ ) cin >> source[i];

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    
    for (int i = 0; i < 6; i ++ ) dijkstra(source[i], dist[i]);
    
    memset(st, 0, sizeof st);//dijkstra和dfs共用一個(gè)st數(shù)組，因此做完dij后要重置st數(shù)組給dfs遍歷用
    
    cout << dfs(1, 0, 0);//1指的是第一層，0指的是start是source[0]也就是車站1（佳佳的家），0指的是當(dāng)前距離為0
    return 0;
}

AcWing 340. 通信線路

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e3 + 10, M = 2 * 1e4 + 10;

int n, m, k;
bool st[N];
int dist[N];
deque<int> q;
int e[M], h[N], w[M], ne[M], idx;

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

bool check(int bound)
{
    memset(st, 0, sizeof st);//因?yàn)檫M(jìn)行多從check，所以要重置
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q.push_back(1);
    
    while (q.size())
    {
        int t = q.front();
        q.pop_front();
        
        if (st[t]) continue;
        st[t] = true;
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], v = w[i] > bound;//如果大于，改邊的邊權(quán)就是1，代表當(dāng)前大于mid的邊增加1
            if (dist[j] > dist[t] + v)
            {
                dist[j] = dist[t] + v;
                if (v == 0) q.push_front(j);
                else q.push_back(j);
            }
        }
    }
    return dist[n] <= k;//判斷到n點(diǎn)的路徑大于mid的邊是否<=k
}

int main()
{
    cin >> n >> m >> k;
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    
    int l = 0, r = 1e6 + 1;//為什么不是1-1e6,l取0是因?yàn)榇鸢缚赡苋?，比如3條邊 k =3,那么答案就不用付錢。 
                           //答案可能取1e6，假如第k+1條邊正好是1e6，但是題目有不連通的情況，因此取1e6+1，判斷是否聯(lián)通
    
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    if (r == 1e6 + 1) cout << "-1";
    else cout << r;
    return 0;
}

AcWing 342. 道路與航線

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 25000 + 10, M = 3 * 5 * 1e4 + 10, INF = 0x3f3f3f3f;

int h[N], e[M], w[M], ne[M], idx;

int id[N], din[N];
vector<int> block[N];

bool st[N];
int dist[N];
queue<int> q;//存儲團(tuán)

int n, mR, mP, S;
int bcnt;

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

void dfs(int u, int bid)
{
    id[u] = bid, block[bid].push_back(u);//記錄每個(gè)團(tuán)內(nèi)有哪些點(diǎn)，有多個(gè)團(tuán)，因此vector是二維的
    
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (id[j] == 0) dfs(j, bid);
    }
}


void dijkstra(int bid)
{
    //雖然多次進(jìn)行dijkstra，但是每次dij遍歷的點(diǎn)的下標(biāo)都是不同的，因此st數(shù)組不用重置
    priority_queue<PII, vector<PII>, greater<PII>> heap;//每個(gè)團(tuán)都用一個(gè)堆去存這個(gè)團(tuán)內(nèi)的點(diǎn)
    
    for (auto u : block[bid])
        heap.push({dist[u], u});
    
    while (heap.size())
    {
        PII t = heap.top();
        heap.pop();
        int distance = t.x, ver = t.y; 
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (id[ver] != id[j] && -- din[id[j]] == 0) q.push(id[j]);//如果兩點(diǎn)不在一個(gè)團(tuán)內(nèi)，將那個(gè)點(diǎn)的入度減1，如果為0，則加入拓?fù)湫蛄兄?/span>
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                if (id[ver] == id[j]) heap.push({dist[j], j});//如果這兩個(gè)點(diǎn)在一個(gè)團(tuán)內(nèi)，再將j點(diǎn)加入當(dāng)前團(tuán)的堆
            }
        }
    }
}


//為什么按拓?fù)湫驎玫阶钌倩ㄙM(fèi)，因?yàn)槊看稳腙?duì)也就是允許訪問的節(jié)點(diǎn)的入度為0，
//這保證我們到此點(diǎn)的所有路徑已經(jīng)被走過并且在此過程中不斷更新最短距離，
//當(dāng)我們開始訪問入度為0的點(diǎn)時(shí)，已經(jīng)沒有其他到此點(diǎn)的路徑去更新它的最短距離

//（沒太懂下面這句話啥意思）
//這道題沒有存團(tuán)之間的最短距離，也沒什么意義，
//而是當(dāng)dij遍歷到有向邊時(shí)更新訪問到的另一個(gè)團(tuán)中點(diǎn)的最短距離，
//實(shí)際上與上面的類似，也可以保證當(dāng)訪問每個(gè)入度為0的點(diǎn)時(shí)，
//團(tuán)類的所有點(diǎn)沒有其他沒有訪問過的從其他團(tuán)到此點(diǎn)的路徑
void topsort()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    
    for (int i = 1; i <= bcnt; i ++ )
    {
        if (din[i] == 0) q.push(i);//入度為0的團(tuán)就加入拓?fù)湫蛄兄?/span>
    }
    
    while (q.size())//遍歷每個(gè)團(tuán)
    {
        int t = q.front();
        q.pop();
        
        dijkstra(t);//dij每個(gè)團(tuán)的同時(shí)更新拓?fù)湫蛄?if (id[ver] != id[j] && -- din[id[j]] == 0) q.push(id[j]);
    }
}

int main ()
{
    cin >> n >> mR >> mP >> S;
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < mR; i ++ )
    {
        int a , b, c;
        cin >> a >> b >> c;
        add (a, b, c), add (b, a, c);
    }
    
    
    for (int i = 1; i <= n; i ++ )//初始化各個(gè)團(tuán)以及各個(gè)團(tuán)有哪些點(diǎn)
    {
        if (id[i] == 0)
        {
            id[i] = ++ bcnt;
            dfs(i, bcnt);
        }
    }
    
    for (int i = 0; i < mP; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c);
        din[id[b]] ++;//P是航線，連接各個(gè)團(tuán)，b是單向邊的目的地，因此b所在的團(tuán)入度+1
    }
    
    topsort();
    
    for (int i = 1; i <= n; i ++ )
    {
        if (dist[i] > INF / 2) cout << "NO PATH" << endl;//因?yàn)橛胸?fù)邊，所以只要判斷結(jié)果大于一個(gè)比較大的數(shù)就說明不連通
        else cout << dist[i] << endl;
    }
    return 0;
}

AcWing 341. 最優(yōu)貿(mào)易

一篇博客解釋了為什么一個(gè)正向建圖求最小值，反向建圖求最大值
根本思想是保證1到n的買賣是連通的
文章來源地址http://www.zghlxwxcb.cn/news/detail-509222.html

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 2 * 2 * 5 * 1e5 + 10;//題目給的有的是雙向邊有的是單向邊，同時(shí)我們需要建兩個(gè)圖再乘2

int q[N], dmin[N], dmax[N];
int n, m;
int w[N];//存儲的是每個(gè)城市的水晶球價(jià)格，而不是邊權(quán)，所以開N的大小
int rh[N], h[N], e[M], ne[M], idx;
bool st[N];


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

void spfa(int h[], int dist[], int type)
{
    int hh = 0, tt = 1;
    
    if (type == 0)
    {
        memset(dist, 0x3f, sizeof dmin);//或者sizeof int
        dist[1] = w[1];
        q[0] = 1;
    }
    else
    {
        memset(dist, -0x3f, sizeof dmax);
        dist[n] = w[n];
        q[0] = n;
    }
    
    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 (type == 0 && dist[j] > min(dist[t], w[j]) || type == 1 && dist[j] < max(dist[t], w[j]))
            {
                if (type == 0) dist[j] = min(dist[t], w[j]);
                else dist[j] = max(dist[t], w[j]);
                
                if (st[j] == 0)
                {
                    q[tt ++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    
}


int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    
    memset(h, -1, sizeof h), memset(rh, -1, sizeof rh);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, type;
        cin >> a >> b >> type;
        add(h, a, b), add(rh, b, a);
        if (type == 2)
            add(h, b, a), add(rh, a, b);
    }
    
    spfa(h, dmin, 0);
    spfa(rh, dmax, 1);
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, (dmax[i] - dmin[i]));//正向圖遍歷從1到i可以買入水晶球的最小值，反向圖遍歷從n到i可以賣出水晶求的最大值，兩者求差
    cout << res;
    return 0;
}

到了這里，關(guān)于算法提高-圖論-單源最短路的綜合應(yīng)用的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！