//0x3f代表无限大
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];  //稠密图，用邻接矩阵
int dist[N];  //用于记录每一个点距离第一个点的距离
bool st[N];  //记录每个点的最短距离是否已经确定

int D_()
{
     memset(dist, 0x3f, sizeof(dist));
     dist[1] = 0;

     for(int i = 0; i < n; i ++)    //有n个点，所以要进行n次迭代
     {
        int t = -1;  //t存储当前访问的点

        for(int j = 1; j <= n; j ++)
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }

        for(int j = 1; j <= n; j ++)   //依次更新每个点所到相邻的点路径值
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        st[t] = true;   
     }
     if(dist[n] == 0x3f3f3f3f) return -1;
     return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min(g[x][y], z);   //如果发生重边的情况则保留最短的一条边
    }
    cout << D_() <<endl;
    return 0;
}

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

typedef pair<int, int> PII;
const int N = 1e6 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int w[N];   //存放边的权重
int dist[N];
bool st[N];

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

int D_()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0,1});    //*****first存储距离，second存储节点编号*****

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;

        if(st[ver]) continue;
        st[ver] = true;

        for(int i =h[ver]; i != -1; i = ne[i])  //***************
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >>z;
        add(x, y, z);
    }
    cout << D_() << endl;
    return 0;
}

//void *memcpy(void *destin, void *source, unsigned n);
//以source指向的地址为起点，将连续的n个字节数据，复制到以destin指向的地址为起点的内存中。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, M = 10010;

struct Edge
{
    int a, b, c;
}edges[M];   //把每个边储存下来

int n, m, k;
int dist[N];
int last[N];  //每次进入第2重循环的dist数组的备份

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for(int i = 0; i < k; i ++)
    {
        memcpy(last, dist, sizeof dist);//************

        for(int j = 0; j < m; j++)
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c); //这句容易错，理解使用dist还是last
        }
    }
}


int main ()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++)
    {
        int x, y , z;
        cin >> x >> y >>z;
        edges[i] = {x, y, z};
    }
    bellman_ford();
    if(dist[n] > (0x3f3f3f3f)/2)  cout << "impossible" <<endl;
    else cout << dist[n] << endl;
    return 0;
}

算法思路

数组模拟队列

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n, m;
int e[N], ne[N], h[N], idx;
int q[N];
int d[N];  //d[i]存储点i的入度

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;

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

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(--d[j] == 0)
                q[++ tt] = j;
        }
    }
    //如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n-1;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));// 初始化
    while(m--)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        d[y] ++;  // y的入度+1
    }
    if(!topsort()) cout << "-1" <<endl;
    else
    {
        for(int i = 0; i < n; i ++) cout << q[i] <<" ";
        cout<<endl;
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100010;
int e[N], ne[N], h[N], idx;
int d[N], n, m;    //d[i]存储头结点到i结点最短距离

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

int bfs()
{
    memset(d, -1, sizeof(d));
    queue<int> q;
    d[1] = 0;
    q.push(1);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; i !=-1; i = ne[i])
        {
            int j = e[i]; ////e[i]表示存在一条边由i指向e[i],通过j来将其存储
            if(d[j] == -1)   //若果没有遍历过j点
            {
                //d[j] = d[i] + 1;***************错误写法
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    return d[n];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof(h));
    while(m--)
    {
        int a,b;
        cin >> a >>b;
        add(a, b);
    }
    cout << bfs() <<endl;
    return 0;
}

// 节点的编号是指上图所画的树中节点的值，范围是从1~n。在本题中，每次输入的a和b就是节点的编号，编号用e[i]数组存储。
// 节点的下标指节点在数组中的位置索引，数组之间的关系就是通过下标来建立连接，下标用idx来记录。idx范围从0开始，如果idx==-1表示空。

// e[i]的值是编号，是下标为i节点的编号。
// ne[i]的值是下标，是下标为i的节点的next节点的下标。
// h[i]存储的是下标，是编号为i的节点的next节点的下标
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010, M = N * 2;
int h[N],e[M],ne[M],idx;//e存值，ne存下一个点的地址,h存链表的头
//注意这个N和M，踩过一次坑
int n;
int ans=N;//此处初始化的意思就是在取min时（很有可能）被赋为第一个值
bool st[N];//看看这个点是否走过

void add(int a, int b) // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u){
    st[u]=true;//说明这个点已经走过去了
    int size=0,sum=0;//(初始化）如果为叶子节点的话，那么sum为0，没有子块
    //size指u节点的单个子树的值
    for(int i=h[u];i!=-1;i=ne[i]){//遍历u的所有子节点
        int j=e[i];//j代表u的联通节点，u->j
        if(st[j]){//这个点已经遍历过，那么看u的下一个子节点
            continue;
        }
        int s=dfs(j);//得到子树点的个数
        size=max(size,s);//比得到所有子树中, 最多的点的个数
        sum+=s;//计算u节点所统领的所有子节点
    }
    size=max(size,n-sum-1);//看看是当前点子树所在的连通块的点数多, 还是父所在的连通块点数多, 获取最多的点数
    ans=min(size,ans);//当前点最多的连通块点数, 是否是所有点中的最小值?
    return sum+1;//返回u节点+所有u节点统领的节点的综合
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n;
    for(int i = 1; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

#include <iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int g[N][N],d[N][N],n,m; //g[N][N]用来存储迷宫,d[x][y]用来存储(x,y)这一点到坐标原点的距离
queue <pair<int,int>> q; //q队列用来存储宽度优先搜素到的路径也就是走迷宫经过哪些点

int bfs()
{
    memset(d, -1, sizeof d);  // 将d所有元素初始化为-1,当d[i][j] = -1时代表没走到过
    d[0][0] = 0;      //位于原点时距离原点的距离为0
    q.push({0, 0});   //将原点入队
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //定义方向向量一共四个方向

    while(q.size())   //当队列非空时执行循环
    {
        auto t = q.front();
        q.pop();
        //遍历四个方向
        for(int i=0;i<4;i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];  //四个方向对应的坐标
            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
                q.push({x, y});  //同时将该点入队
            }
        }
    }
    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;
}

、

C++ 代码

#include<iostream>
using namespace std;
const int N = 10;
int state[N];
int path[N];
int n;

//dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
void dfs(int u)
{ 
    if(u > n)  //数字填充完了，进行输出
    {
        for(int i = 1; i <= n; i++)  //输出方案
            cout << path[i] << " ";
        cout << endl;
    }
    for(int i = 1; i <= n; i++)    // 空位上的数字可能是1~n
    {
        if(!state[i])    //如果数字i并没有被用过
        {
            state[i] = 1;  //数字被用，修改状态
            path[u] = i;   //将i加入下一位
            dfs(u + 1);    //填下一位
            state[i] = 0;  //回溯，将i取出
        }
    }
}

int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

、

拉链法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;
int h[N], e[N], ne[N], idx;
//h[]散列表保存头节点的下标
// e[]保存值，ne[]保存前一个值的下标，idx是链表的索引

//向哈希表中插入一个数x
void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;
}

//在哈希表中查找对应元素是否存在
bool find(int x)
{
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i])
    {
        if(e[i] == x)
            return true;
    }
    return false;
}

int main()
{
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);   //散列表初始化
    while(n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op == 'I') insert(x);
        else
        {
            if(find(x)) cout << "Yes" <<endl;
            else cout << "No" <<endl;
        }
    }
    return 0;
}

开放寻址法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003, null_ = 0x3f3f3f3f;
int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
    int t = (x % N + N) % N;
    while(h[t] != null_  &&  h[t] != x)
    {
        t ++;
        if(t == N) t = 0;
    }
    return t;
}
int main()
{
    int n;
    scanf("%d", &n);
    memset(h, 0x3f, sizeof h);
    while(n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op == 'I') h[find(x)] = x;
        else
        {
            if(h[find(x)] == null_) cout << "No" <<endl;
            else cout << "Yes" <<endl;
        }
    }
    return 0;
}