//858.Prim算法求最小生成树
//与Dijkstra算法的区别：
//Prim算法迭代n次，dist存储的是操作点到集合的最短距离
//Dijkstra算法的dist存储的是操作点到点1的距离
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=510,INF=0x3f3f3f3f;

int n,m;
int g[N][N]; //存储图
int dist[N]; //存储各个节点到生成树的距离
bool st[N]; //节点是否被加入到生成树中

int prim() //如果图不连通返回INF, 否则返回res
{
    memset(dist,0x3f,sizeof dist);

    int res=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        //寻找离集合S最近的点并将最近的点赋值给t
        if(i&&dist[t]==INF) return INF; //判断是否连通，有无最小生成树
        if(i) res+=dist[t];
        //cout << i << ' ' << res << endl;
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
        //用t更新其他点到集合的距离
        st[t]=true; //更新最新S的权值和
    }

    return res;
}

int main()
{
    scanf("%d%d",&n,&m);

    memset(g,0x3f,sizeof g);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c);
    }

    int t=prim(); //临时存储防止执行两次函数导致最后仅返回0

    if(t==INF) puts("impossible");
    else printf("%d\n",t);

    return 0;
}

https://www.acwing.com/solution/content/6320/
这个作者总结得得非常好，可以参考一下，便于理解。

//849.Dijkstra求最短路I
//Dijkstra
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=510;

int n,m;
int g[N][N]; //为稠密阵所以用邻接矩阵存储
int dist[N];  //用于记录每一个点距离第一个点的距离
bool st[N]; //用于记录该点的最短距离是否已经确定

int dijkstra()
{
    memset(dist,0x3f,sizeof dist); //初始化距离，0x3f代表无限大
    dist[1]=0; //第一个点到自身的距离为0

    for(int i=0;i<n;i++) //以下标为i的点为参照点进行n次迭代
    {
        int t=-1; //t存储当前访问的点
        for(int j=1;j<=n;j++) //这里的j代表的是从j号点开始，实际从j+1号点开始
            if(!st[j]&&(t==-1||dist[t]>dist[j])) //第一次判断语句永远执行（t==-1）
                t=j;
        //下标为i的点的最短距离未确定，并且当前访问的点的距离比j点大，则当前访问j点
        //if(t==n) break; //提前结束

        st[t]=true; //t点最短距离确定

        for(int j=1;j<=n;j++) //用t依次更新每个点所到相邻的点路径值
            dist[j]=min(dist[j],dist[t]+g[t][j]);
            //第一次执行该for循环语句时，与点1有直接相连的都作为最近距离的点
            //若无直接连接，则dist为无穷大，即0x3f3f3f3f
    }

    if(dist[n]==0x3f3f3f3f) return -1; //如果第n个点路径为无穷大即不存在最低路径
    return dist[n];
}

int main()
{
    scanf("%d%d",&n,&m);

    memset(g,0x3f,sizeof g); //初始化图，每个点初始为无限大
    /*
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) g[i][j]=0;
            else g[i][j]=INF;
    */
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c); //如果发生重边的情况则保留最短的一条边
    }

    int t=dijkstra();

    printf("%d\n",t);

    return 0;
}

//848.有向图的拓扑序列
//一个无环图一定至少存在一个入度为0的点
//一个有向无环图的拓扑序列不一定是唯一的
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N]; //q表示队列，d表示点的入度
//h[N]邻接表存储树，有n个节点，所以需要n个队列头节点（初始化指向-1）
//e[M]存储元素
//ne[M]存储列表的next值
//idx单链表指针
//n为题目所给的输入，n个节点
//m为m条边
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++; //此处有两种含义的下标
}

bool topsort()
{
    int hh=0,tt=-1;

    for(int i=1;i<=n;i++)
        if(!d[i])
            q[++tt]=i; //将入度为0的点入队

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

        for(int i=h[t];i!=-1;i=ne[i]) //i为h[t]指向的节点的下标
        {
            int j=e[i]; //j为下标对应的元素值，即节点
            d[j]--; //删除点t指向点j的边
            if(d[j]==0) q[++tt]=j; //若点j的入度为零，则将点j入队
        }
    }

    return tt==n-1;
    //表示如果n个点都入队了话，那么该图为拓扑图，返回true，否则返回false
}

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); //把b插入到a后面，即a->b
        d[b]++; //b的入度加1
    }

    if(topsort())
    {
        for(int i=0;i<n;i++) printf("%d ",q[i]);
        puts("");
    }
    else puts("-1");

    return 0;
}

//847.图中点的层次
//广度优先遍历
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
//h[N]邻接表存储树，有n个节点，所以需要n个队列头节点（初始化指向-1）
//e[M]存储元素
//ne[M]存储列表的next值
//idx单链表指针
//n为题目所给的输入，n个节点
//d[]存储每个节点离起点的距离，d[1]=0
//q[]存储层次遍历序列，0号节点是编号为1的节点
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++; //此处有两种含义的下标
}

int bfs()
{
    int hh=0,tt=0;
    q[0]=1; //0号节点是编号为1的节点

    memset(d,-1,sizeof d);

    d[1]=0; //存储每个节点离起点的距离

    while(hh<=tt) //当队列不为空时
    {
        int t=q[hh++]; //取出队列头节点

        for(int i=h[t];i!=-1;i=ne[i]) //遍历t节点的每一个邻边
        {
            int j=e[i];
            if(d[j]==-1) //如果j没有被扩展过
            {
                d[j]=d[t]+1; //d[j]存储j节点离起点的距离，并标记为访问过
                q[++tt]=j; //把j结点压入队列
            }
        }
    }

    return d[n];
}

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);
    }

    cout<<bfs()<<endl;

    return 0;
}

//846.数的重心
//深度优先遍历
//时间复杂度O(n+m)
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010,M=N*2;
//以有向图的格式存储无向图，所以每个节点至多对应2n-2条边
int n;
int h[N],e[M],ne[M],idx;
bool st[N]; //记录节点是否被访问过，访问过则标记为true
//h[N]邻接表存储树，有n个节点，所以需要n个队列头节点（初始化指向-1）
//e[M]存储元素
//ne[M]存储列表的next值
//idx单链表指针
//n为题目所给的输入，n个节点

int ans=N; //表示重心的所有的子树中，最大的子树的结点数目

void add(int a,int b) //a所对应的单链表中插入b，a作为根
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++; //此处有两种含义的下标
}

//以u为根的子树中点的数量
int dfs(int u)
{
    st[u]=true; //标记一下，已经被搜索过了

    int sum=1,res=0;
    //sum存储以u为根的树的节点数，包括u（初始化为1），如图中的4号节点
    //res存储删掉某个节点之后，最大的连通子图节点数
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        //因为每个节点的编号都是不一样的，所以用编号为下标来标记是否被访问过
        if(!st[j]) //若节点未被访问过
        {
            int s=dfs(j); //u节点的单棵子树节点数，如图中的size值
            res=max(res,s); //记录最大联通子图的节点数
            sum+=s; //以j为根的树的节点数
        }
    }
    res=max(res,n-sum);
    //若为叶子节点，则最大为n-sum，即n-1
    ans=min(ans,res); //第一次比较后最小值为res
    return sum;
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h); //memset按字节赋值

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

    dfs(1); //可以任意选定一个节点开始（u<=n）

    cout<<ans<<endl;

    return 0;
}

//844.走迷宫
//BFS-广度优先遍历
//增加路径输出
//本题：若某坐标点已经被访问过，则不会被再次访问，避免得到更长的无用路径
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int,int> PII;

const int N=110;

int n,m;
int g[N][N];
int d[N][N];
PII q[N*N],Prev[N][N]; //q存储坐标，Prev存储路径坐标

int bfs()
{
    int hh=0,tt=0;
    q[0]={0,0};
    memset(d,-1,sizeof d);
    d[0][0]=0; //判重

    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //下一步共上、下、左、右四个方向

    while(hh<=tt) //当队列不为空时
    {
        auto t=q[hh++];

        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i]; //更新x和y
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1) //若符合条件
            {
                d[x][y]=d[t.first][t.second]+1; //移动次数加1，即坐标(x,y)处代表的次数
                Prev[x][y]=t; //路径坐标，(x,y)为新坐标，t为老坐标
                q[++tt]={x,y}; //把新坐标加到队尾
            }
        }
    }

    int x=n-1,y=m-1;
    while(x||y) //x或y不等于0，即从最后一个点往前走
    {
        cout<<x<<' '<<y<<endl;
        auto t=Prev[x][y];
        x=t.first,y=t.second;
    }

    return d[n-1][m-1];
}

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

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];

    cout<<bfs()<<endl;

    return 0;
}

memset(h,0x3f,sizeof h); //memset按字节赋值
    //int是4个字节，memset会把int的4个字节全部初始化为0x3f
    //-1在C++中表示每个位上的数都是1

写给自己看的笔记，如有冒犯，请联系我删除。

//843.n-皇后问题
//由样例的输出过程分析：输出时行列颠倒，把样例向左旋转90°后的分布符合x-y轴坐标系
#include<iostream>

using namespace std;

const int N=20;

int n;
char g[N][N];
bool col[N],dg[N],udg[N];
//col[]为列，dg[]为对角线（左上右下），udg[]为反对角线（左下右上）
void dfs(int u)
{
    if(u==n) //u+1后成层数已经超出范围（层数从0开始）
    {
        for(int i=0;i<n;i++) puts(g[i]); //以行为单位输出，即g[i][u]
        puts("");
        return;
    }
    //u相当于x（列/横坐标），i相当于y（行/纵坐标）
    //用截距来表示某条对角线
    for(int i=0;i<n;i++)
        if(!col[i]&&!dg[u+i]&&!udg[n-u+i]) //当该列无元素，并且对角线和反对角线也无元素
        {
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[n-u+i]=true; //标记该列，对角线和反对角线已被占用
            dfs(u+1); //递归下一层
            col[i]=dg[u+i]=udg[n-u+i]=false; //恢复现场
            g[u][i]='.'; //恢复现场
        }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.'; //初始化

    dfs(0); //从第0层开始递归

    return 0;
}

//842.排列数字
//DFS，数据结构：队列（stack），空间：O(h)，不具最短性
#include<iostream>

using namespace std;

const int N=10;

int n;
int path[N]; //存储状态
bool st[N]; //记录数字i是否已经被用过

void dfs(int u)
{
    if(u==n) //u+1后成层数已经超出范围（层数从0开始）
    {
        for(int i=0;i<n;i++) printf("%d ",path[i]);
        puts("");
        return;
    }

    for(int i=1;i<=n;i++)
        if(!st[i]) //当前数i没有被用过
        {
            path[u]=i; //把数i放到当前位置上去
            st[i]=true; //记录数字i是否已经被用过
            dfs(u+1); //递归下一层
            //path[u]=0; //无需恢复，path[u]会被不断覆盖
            st[i]=false; //恢复现场
        }
}

int main()
{
    cin>>n;

    dfs(0); //从第0层开始递归

    return 0;
}