multiset存放具体方案,用for输出

acwing842：dfs:递归

#include <bits/stdc++.h>

using namespace std;

const int N = 10 ;

int n ;
multiset<vector<int> > res;
vector<int> path;
bool st[N];


void dfs(int u)
{
    if (u > n) //u == n 时 第n个位置还未填
    {
        res.insert(path);
        return;
    }
    for (int i = 1 ; i <= n ; i ++)
    {
        if (!st[i])
        {   
            st[i] = true;
            path.push_back(i); 
            dfs(u + 1);
            st[i] = false;
            path.pop_back();
        }
    }

}

int main()
{
    cin >> n ;
    dfs(1);
    for (auto vec : res )
    {
        for (auto x : vec )
            cout << x << ' ' ;
        cout << endl ;
    }

    return 0;

}

acwing844:bfs：队列

#include <bits/stdc++.h>

using namespace std;

typedef pair<int , int > PII ;

const int N = 110 , M = 110 ;

int g[N][M];
int n , m ;
PII d[4] = {{1,0} , {0,1} , {-1,0} , {0,-1}};
int dist[N][M] ;

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

    queue<PII > q;
    q.push({1,1});

    while (q.size())//
    {
        auto t = q.front();
        q.pop();
        int x = t.first , y = t.second ;

        for (int k = 0 ; k < 4 ; k ++)
        {
            int dx = d[k].first , dy = d[k].second;
            int i = x + dx , j = y + dy;
            if (i >= 1 && i <= n && j >= 1 && j <= m && dist[i][j] == -1 && g[i][j] == 0)
            {
                q.push({i,j});         
                dist[i][j] = dist[x][y] + 1;
            }
        } 
    }

}

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

    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1 ; j <= m ; j ++)
            cin >> g[i][j];
    bfs();
    cout << dist[n][m] << endl;
    return 0 ;
}

最短路径：若权值相等可以用bfs求最短路 ； 权值不等用dijkstra、bellman-ford、spfa、floyd，其中dijkstra不能处理负边，floyd不能处理负环

acwing847 : bfs(权值相等)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

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

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

void bfs()
{
    memset(dist , -1 ,sizeof dist);//
    dist[1] = 0;

    queue<int > q;
    q.push(1);

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = true;

        for (int i = h[t] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if (dist[j] == -1)
            {
                dist[j] = dist[t] + 1;
                q.push(j);
            }
        }
    }

}

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

    memset(h , -1 , sizeof h);
    for (int i = 0 ; i < m ; i ++)
    {
        int a , b ;
        cin >> a >> b ;
        add(a , b);
    }

    bfs();

    cout << dist[n] << endl ;

    return 0 ;
}

acwing847: dijkstra//需要注意堆优化使用到的优先队列默认是大根堆，需要再改成小根堆。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int , int> PII;

const int N = 1e5+10;

int e[N] , h[N] , ne[N] , w[N] , idx ;
int n , m;
int dist[N];
bool st[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;

    priority_queue<PII , vector<PII > , greater<PII> > q; 
    q.push({0 , 1});

    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int i = t.second , d = t.first;

        if (st[i]) continue; //这一步y总说是减少冗余，是因为本题有重边吗。如果是简单图直接st[i] = true就可以。
        else st[i] = true;

        for (int u = h[i] ; u != -1 ; u = ne[u])
        {
            int j = e[u];
            if (dist[j] > d + 1)
            {
                dist[j] = d + 1;
                q.push({dist[j] , j});
            }
        }
    }

}

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

    memset(h , -1 , sizeof h);
    for (int i = 0 ; i < m ; i ++)
    {
        int a , b ;
        cin >> a >> b ;
        add(a , b);
    }

    bfs();

    if (dist[n] != 0x3f3f3f3f) cout << dist[n] << endl ;
    else puts("-1");

    return 0 ;
}