單源最短路的建圖方式

AcWing 1129. 熱浪

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2500 + 10, M = 6200 * 2 + 10;
int q[N], dist[N];
bool st[N];
int e[M], h[N], w[M], ne[M], idx;//理解鏈表存儲圖的本質(zhì)，h只需要開N，與節(jié)點(diǎn)數(shù)相同
int n, m, S, T;

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

void spfa()
{
    memset(st, 0, sizeof st);
    
    memset(dist, 0x3f, sizeof dist);
    
    dist[S] = 0;//S是起點(diǎn)，起點(diǎn)到自己的距離為0
    
    int hh = 0, tt = 1;//默認(rèn)S先占一個位置，因此tt要從1開始，同時這也滿足進(jìn)入while循環(huán)的條件hh！=tt
    q[0] = S;
    st[S] = true;
    
    
    while (hh != tt)//循環(huán)隊列不是<= 而是！
    {
        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;//循環(huán)隊列，st數(shù)組的存在隊列里面最多存儲N個點(diǎn)，一個點(diǎn)可能多次入隊，
                                        //我們不知道大概這個隊列應(yīng)該開多大，同時為了節(jié)省空間我們用循環(huán)隊列
                    st[j] = true;
                }
            }
        }
    }
    
}
int main ()
{
    cin >> n >> m >> S >> T;
    
    memset(h, -1, sizeof h);//這個不能放在spfa里面，必須在add之前就初始化好h數(shù)組。。之前傻逼了
    
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    
    spfa();
    
    cout << dist[T];
    return 0;
}

AcWing 1128. 信使

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int d[N][N];

int main()
{
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    
    for (int i = 1; i <= n; i ++ ) d[i][i] = 0;//初始化，每個點(diǎn)作為源點(diǎn)到他自己的距離為0
    
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = d[b][a] = min(d[a][b], c);//最短路問題有重邊，取最短的即可
    }
    
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);//floyd本質(zhì)是動態(tài)規(guī)劃，劃分子集的時候可以以最后到達(dá)j前的最后一個點(diǎn)是k來劃分，k這一維可以省略
    
    int ans = 0;
    for (int i = 1; i <= n; i ++ )
        if (d[1][i] == INF)
        {
            ans = -1;
            break;
        }
        else ans = max(ans, d[1][i]);//不是ans +=  d[1][i]，因為最遠(yuǎn)的的i點(diǎn)都送到了，其他的點(diǎn)也肯定送到了，題目說了信使送信是擴(kuò)散的
    
    cout << ans;
    return 0;
}

AcWing 1127. 香甜的黃油

建圖 找出一個牧場，它到其他牧場的距離之和最小

//建圖 找出一個牧場，它到其他牧場的距離之和最小

#include <iostream>
#include <cstring>

using namespace std;

const int N = 800 + 10, M = 1450 * 2 + 10, INF = 0x3f3f3f3f;

int n, p, m;
int id[510];
int e[M], w[M], ne[M], h[N], idx;//這里定義的時候按照牧場數(shù)定義，本質(zhì)求的還是牧場之間的最短路，奶牛只不過和牧場之間有一些映射關(guān)系罷了
int q[N], st[N];//st一般如果只有一組測試數(shù)據(jù)不用多次初始化
int dist[N];


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

int spfa(int start)
{
    memset(dist, 0x3f, sizeof dist);
    
    int hh = 0, tt = 1;
    q[0] = start, dist[start] = 0, st[start] = true;
    
    while (hh != tt)
    {
        int t = q[hh ++ ];
        st[t] = false;
        if (hh == N) hh = 0;
        
        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 ans = 0;
     
    // for (int i = 0; i < n; i ++ )
    // ans += dist[id[i]];
    
    for (int i = 0; i < n; i ++ )
    {
        int j = id[i];
        if (dist[j] == INF) return INF;//不知道為啥非要這么特判，題目也沒說有的不可達(dá)
        ans += dist[j];
    }
     return ans;
}

int main ()
{
    cin >> n >> p >> m;
    for (int i = 0; i < n; i ++ ) cin >> id[i];
    
    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 ans = INF;
    //因為牧場的編號是從1開始的，所以遍歷要從1開始而不是0
    for (int i = 1; i <= p; i ++ ) ans = min(ans, spfa(i));
    
    cout << ans;
    return 0;
}

AcWing 1126. 最小花費(fèi)

我是這么理解的，djsktra是一個貪心的思想，加法里面不能加負(fù)數(shù)我就不說了
求乘法最大值的時候為什么邊權(quán)必須0-1，因為在乘法最大值里面有一個邊權(quán)大于1的話那不就等價于求加法最小值的時候有一個邊權(quán)為負(fù)數(shù)的么，dj是貪心的思想，每次出隊的時候必須都是最值不能在改變了，而乘法最大值中邊權(quán)大于1會破壞這個貪心的思路。

一開始建圖沒想到是無向圖debug了好久，甚至以為是double精度問題

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2010;//用鄰接表存儲圖的時候不需要定義邊的條數(shù)，有重邊的情況下根據(jù)題意去最大值或最小值即可

bool st[N];
double dist[N];
double g[N][N];

int n, m, S, T;

void  dijkstra()
{
    dist[S] = 1;
    //st[S] = true;不能把源點(diǎn)先變?yōu)閠rue，因為我們還需要源點(diǎn)去更新源點(diǎn)周圍的點(diǎn)
                                  //n個點(diǎn)，在邊權(quán)滿足條件的情況下，每個點(diǎn)都要遍歷一次，因此需要遍歷n次
    for (int i = 1; i <= n; i ++ )//for (int i = 0; i < n; i ++ ) 循環(huán)n次就行了，下標(biāo)從1和0開始都可以，但是下面的for涉及下標(biāo)了，看題意是下標(biāo)從0還是1開始
    {
        int t = -1;                  //j是具體的點(diǎn)的下標(biāo)，題目說了 下標(biāo)>=1   
        for (int j = 1; j <= n; j ++ )//貪心：找到當(dāng)前沒確定的點(diǎn) 且 離源點(diǎn)最近的點(diǎn)
        {
            if (!st[j] && (t == -1 || dist[t] < dist[j]))
                t = j;
        }
        st[t] = true;
        
        for (int j = 1; j <= n; j ++ )
        {
            dist[j] = max(dist[j], dist[t] * g[t][j]);//動態(tài)規(guī)劃，用距離源點(diǎn)最近的點(diǎn)去更新其他點(diǎn)到源點(diǎn)的距離
        }
    }
}


int main ()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        
        g[a][b] = g[b][a] = max(g[a][b], (100.0 - c) / 100);
        //g[a][b] = max(g[a][b], (double)(100.0 - c) / 100);
        //double z = (100.0 - c) / 100;
        //g[a][b] = g[b][a] = max(g[a][b], z);
    }
    
    cin >> S >> T;
    
    dijkstra();
    
    printf("%.8lf\n", 100 / dist[T]);

    return 0;
}

AcWing 920. 最優(yōu)乘車

這題的輸入輸出挺惡心的，對了，輸入小于10萬就可以用cin
getline
sstream
將一輛車可以到達(dá)的所有站點(diǎn)之間連接都連接一條邊，那就是要cn2條邊具體我描述的不太好，可以去看這題的視頻講解。

#include <iostream>
#include <cstring>
#include <sstream>
#include <cstdio>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
bool g[N][N];
int stop[N];
int q[N], dist[N];
int n, m;

void bfs ()
{
    memset(dist, 0x3f, sizeof dist);
    int hh = 0, tt = 0;
    q[0] = 1;
    dist[1] = 0;//dist記錄的是從源點(diǎn)到該點(diǎn)需要乘坐多少次大巴，從1號點(diǎn)到1號點(diǎn)在只需要乘坐0次大巴
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        
        for (int i = 1; i <= n ; i ++ )//公交站牌的下標(biāo)是從1開始的不是0
        {
            if (g[t][i] && dist[i] > dist[t] + 1)
            {
                dist[i] = dist[t] + 1;
                q[++ tt] = i;
            }
        }
    }
}

int main ()
{
    cin >> m >> n;//這題是先輸入m,在輸入n比較惡心
    string line;
    getline(cin, line);//將第一行的換行接受掉
    
    while (m -- )
    {
        getline(cin, line);//相比于cin，這是讀一整行可以讀取到空格換行等
        stringstream ssin(line);//把字符串轉(zhuǎn)化為int
        int cnt = 0, p;
        while (ssin >> p)  stop[cnt ++ ] = p;
        
        for (int i = 0; i < cnt; i ++ )
            for (int j = i + 1; j < cnt; j ++ )
             g[stop[i]][stop[j]] = true;
    }
    
    bfs();
    
    if (dist[n] == INF) puts("NO");
    else cout << max(dist[n] - 1, 0);//題目要輸出的是換乘次數(shù) 如果換乘次數(shù)為0，則dist[n] - 1 = -1(因為只用一輛車到達(dá)目的地的換乘次數(shù)是0，但是乘坐的不同大巴種類為1)
                                     //,但題目要輸出的是0 ，因此要特判一下
    
    return 0;
}

AcWing 903. 昂貴的聘禮

w數(shù)組很精髓，level數(shù)組很牛逼，虛擬源點(diǎn)結(jié)合w數(shù)組更nb，同時注意dijkstra里面的for循環(huán)下標(biāo)的含義，到底是控制循環(huán)次數(shù)，還是真正映射的是下標(biāo)文章來源地址http://www.zghlxwxcb.cn/news/detail-475521.html

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

bool st[N];
int w[N][N], dist[N], level[N];
int m, n;


int dijkstra(int down, int up)
{
    
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);//不知道這里為什么會wa，明明其實一般如果沒有多組數(shù)據(jù)不需要這個初始化，全局的st默認(rèn)就是false
    //st[0] = true;經(jīng)常犯這個錯，因為我們需要用源點(diǎn)來更新它周圍的點(diǎn)到它的距離，dj其實就是dfs，只不過權(quán)值不是1罷了
    dist[0] = 0;
    for (int i = 1; i <= n + 1; i ++ )//多了一個虛擬源點(diǎn)，因此要循環(huán)n + 1次才能確定n+1件物品到源點(diǎn)的最短距離，x加上虛擬源點(diǎn)一共有n + 1個物品，x
    {                                 //dj貪心的思想就是每次循環(huán)都可以確定一個節(jié)點(diǎn)到源點(diǎn)的最短距離，再用這個節(jié)點(diǎn)去更新它到其他點(diǎn)的距離
        int t = -1;
        for (int j = 0; j <= n; j ++ )//這里遍歷的時候遍歷的是編號，而不是保證次數(shù)，題目編號下標(biāo)從1開始，但是我們虛擬源點(diǎn)的下標(biāo)是0
        if (!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j;
        st[t] = true;
        
        for (int j = 1; j <= n; j ++ )
        {
            if (level[j] >= down && level[j] <= up) dist[j] = min(dist[j], dist[t] + w[t][j]);//dp的思想
        }
    }
    
    return dist[1];
}





int main()
{
    cin >> m >> n;
    memset(w, 0x3f, sizeof w);
    
    for (int i = 1; i <= n; i ++ )w[i][i] = 0; //用第i個物品換第i個物品需要額外＋0元
    
    for (int i = 1; i <= n; i ++ )
    {
        int price, cnt;
        cin >> price >> level[i] >> cnt;
        w[0][i] = min(price, w[0][i]);//可以不用min，但以防萬一么 雖然我不知道為什么要取min題目沒說會輸入重復(fù)數(shù)據(jù)，但這個意思就是什么物品都不帶換第i個物品需要它自身原來的價格

        while (cnt -- )
        {
            int id, cost;
            cin >> id >> cost;
            
            //w[id][i] =  cost;
            w[id][i] = min(w[id][i], cost);// 可以不用min，但以防萬一么    用序號為id的物品換物品i需要＋cost元
        }
    }
    
    int res = INF;
    //最終需要換的物品為物品1，因此我們以物品1為基底，遍歷“圖"可以到達(dá)的節(jié)點(diǎn)（即可以使用的物品有哪些）
    for (int i = level[1] - m; i <= level[1]; i ++ ) res = min(res, dijkstra(i, i + m));
    
    cout << res << endl;
    return 0;
}

到了這里，關(guān)于算法提高-圖論-單源最短路的建圖方式的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！