最短路问题

逃离我推掉我的手 2023-10-04 11:57 55阅读 0赞

#### 文章目录 ####

*  最短路问题
 *   *  一.朴素dijkstra算法
     *  二.堆优化版dijkstra 算法
     *  三.Bellman-Ford算法
     *  四.spfa 算法
     *  五.floyd算法
     *  六.一些题目
     *   *   *  题1：信使
             *  题2：香甜的黄油
             *  题3：最小花费
     *  七.附录（四种解法模板，转载自\[AcWing\](https://www.acwing.com/blog/content/405/)）
     *   *   *  1.朴素dijkstra算法
             *  2.堆优化版dijkstra
             *  3.Bellman-Ford算法
             *  4.spfa 算法
             *  5.floyd算法

## 最短路问题 ##

> 序：最短路问题：求图中某个点到另一个点所经过权重和最小的路径的长度。**（以下的n均表示点数，m均表示边数）**

### 一.朴素dijkstra算法 ###

> 原理：dijkstra算法以广度优先搜索为基础，从一个源点中心按广度优先搜索依次扩展每一个点，其采用了贪心的思想，我们可以用数组dist\[\]表示源点到每个点的最短路径的距离。然后按接下来的步骤求解：

> 1.  初始化：设置一个dist\[N\]数组，存储每个点到源点的距离，设x为源点，初始化dist\[\]所有数据为无穷大，代码表示为`memset(dist, 0x3f, sizeof dist);`对于源点自身自然有`dist[x]=0`。
> 2.  题目初始条件初始化：对于dijkstra算法我们用g\[\]\[\]表示每两个点的距离，g初始化为无穷大，`memset(g,0x3f,sizeof g)`;按题目给出的数据依次更新每两个点之间的最小距离即可。注意有向图和无向图的区别。
> 3.  更新：我们可以用一个集合A表示已经确定最短距离的点，用t表示不再集合A中而且距离源点最近的点，在用t更新其它不再A中的其它点到源点的最短距离。在编码过程中，我们可以用一个bool数组st\[\]模拟集合A。第一次可以用源点更新其它点，后面依次用距离源点最小的点更新其它点。最多更新n次就可以得出答案。

例子分析：**求点1到点4的最短距离**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70_pic_center]

> 第一步：dist\[1\]=0,dist\[2\]=INF,dist\[3\]=INF,dist\[4\]=INF;（INF表示正无穷）
> 
> 第二步：g\[1\]\[2\]=3,g\[2\]\[3\]=3,g\[2\]\[4\]=5,g\[3\]\[4\]=1;其它个g\[\]\[\]为INF；
> 
> 第三步：更新：
> 
> （1）用源点1更新其他点有：dist\[2\]=dist\[1\]+g\[1\]\[2\]=3;点1进入集合A，st\[1\]=true;
> 
> (2)其它点中点2距离源点1最近，t=2；用点2更新其他点到源点的最短距离，dist\[3\]=dist\[2\]+g\[2\]\[3\]=6,dist\[4\]=dist\[2\]+g\[2\]\[4\]=8;点2进入集合A，st\[2\]=true;
> 
> (3)同上分析，这次t=3，dist\[3\]+g\[3\]\[4\]=7<dist\[4\];所以dist\[4\]被更新为7,st\[3\]=true;
> 
> (4)最后一次更新，点4更新其它点结果不变，st\[4\]=true;至此更新结束，得出答案dist\[4\]=7.
> 
> 可以得出每次更新可以将一个点进入集合A,因此在题目有解的情况下，我们最多n次更新就可以将所有点与源点的最短距离求出。即可以得出答案。

### 二.堆优化版dijkstra 算法 ###

> 原理:对于边数太多的图用朴素的dijkstra的算法会超时，因此必须要优化。这里我们数据结构堆优化（priority\_queue)。该方法本质上是用更大的空间换取了更小的时间，达到了对时间复杂度的优化。这里我们用邻接表存储边和边的权值，加边代码如下，详细请看1.[AcWing][]；我们用 priority\_queue<PII, vector, greater> heap （PII为pair<int,int>）;存取每个点到源点的距离及自己的编号，pair以第一键值排序。每次选出堆顶（此时堆顶的点必然是距离源点距离最短的点）的点用其来更新其他点与源点的距离，已经用于更新过其他点的点进入集合A（st\[i\]=true),表示已经确定了最短距离的点。直到堆为空，全部点到源点最短距离更新完成。

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

### 三.Bellman-Ford算法 ###

> 原理：遍历n次，每次依次从小到大遍历所有边。这里用结构体存边及边权。
> 
> 这里需要遍历n次的原因：
> 
> 最坏情况下，源点到目标点最多会经过n-1条边，每次遍历最坏只会更新一个点，只有n次遍历可以保证目标点到源点的距离最短。
> 
> 该解法不允许出现负权回路。该算法可以求解有边数限制求最短路的题目，当求解距离源点不超过k条边时遍历k次，每次从小到大求每条边两个点到源点的最短距离。下面一个例子来具体分析Bellman-Ford算法。

例子分析：**求点1到点4之间的最短距离**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70]

> 第一步：将所有边存入结构体Edges；
> 
> 第二步：更新：
> 
> 第一次遍历：
> 
> 边（1,2）,dist\[2\]=dist\[1\]+w=3;
> 
> 边（2,3）,dist\[3\]=dist\[2\]+w=6;
> 
> 边（2,4），dist\[4\]=dist\[2\]+w=8;
> 
> 边（3,4），dist\[4\]=dist\[3\]+w=7;
> 
> 可以看出这道题第一次遍历即可得到最短距离。

### 四.spfa 算法 ###

> 原理：该算法是对Bellman-Ford算法的优化，我们在使用Bellman-Ford算法时条边都需要遍历更新，但是并不一定每条边都会被更新，这里我们用queue优化，把源点放入queue，只要队列不为空，每次更新只要有点到源点的距离变小而且该点不在queue中就将该点放入queue； 最后每个点到源点距离必然是最短距离，queue为空退出更新，这里用一个bool数组st\[\]表示点是否在队列，st\[i\]为false不在，st\[i\]为true在；该算法大部分情况下时间复杂度是最低的,负环回路不可用。下面一个例子来具体分析spfa算法。

例子分析：**求点1到点4之间的最短距离**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qYSZjAVp-1619500179595)(file://C:\\Users\\LLLBJ\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210426210903420.png?lastModify=1619486064)\]][img-qYSZjAVp-1619500179595_file_C_Users_LLLBJ_AppData_Roaming_Typora_typora-user-images_image-20210426210903420.png_lastModify_1619486064]

> 第一步：用邻接表储存每条边的信息；
> 
> 第二步：将源点1进入队列；
> 
> 第三步：更新：
> 
> 点1：点1出队，st\[1\]=false;dist\[2\]=3,2入队列，st\[2\]=true;
> 
> 点2：点2出队，st\[2\]=false;dist\[3\]=6,dist\[4\]=8,3和4入队，st\[3\]=true,st\[4\]=true;
> 
> 点3：点3出队，st\[3\]=false;dist\[4\]=7,4已经在队中无须入队；
> 
> 点4：点4出队,st\[4\]=false,queue为空退出。
> 
> 更新完成得到dist\[4\]=7;

### 五.floyd算法 ###

> 原理：该算法是一种动态规划的算法，较前面几个算法更容易理解，可以求出任意两个点之间的最短距离，缺点是时间复杂度太高，不可以解决负权回路问题。我们用邻接矩阵d\[\]\[\]表示每两个点之间的距离，d\[i\]\[j\]表示i到j之间的最短距离，则i到j可以直接从i到j，也可以是i经过若干点到j的最短距离。具体步骤如下：
> 
> 1.  **初始化：**
>     
>         for (int i = 1; i <= n; i ++ )
>                 for (int j = 1; j <= n; j ++ )
>                     if (i == j) d[i][j] = 0;
>                     else d[i][j] = INF;
>     
>     如果i==j则d\[i\]\[j\]=0,否则全部初始化为INF。
> 2.  题目初始条件初始化：根据题目条件初始化每两个点之间的距离的d\[i\]\[j\];
> 3.  更新：循环n次，每次d\[i\]\[k\]+d\[k\]\[j\]表示i经过k转移到j的最短距离,如果小于d\[i\]\[j\]，则更新d\[i\]\[j\];
>     
>         void floyd()
>         {
>             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]);
>         }

例子分析：**求任意两个点之间的最短距离**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8qGjtnwv-1619500179598)(C:\\Users\\LLLBJ\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210426210903420.png)\]][img-8qGjtnwv-1619500179598_C_Users_LLLBJ_AppData_Roaming_Typora_typora-user-images_image-20210426210903420.png]

> 第一步：d\[1\]\[2\],d\[2\]\[3\]=3,d\[2\]\[4\]=5,d\[3\]\[4\]=1其余都为INF；
> 
> 第二步：更新：
> 
> k=1,不变
> 
> k=2，dist\[1\]\[3\]=dist\[1\]\[2\]+dist\[2\]\[3\]=6,dist\[1\]\[4\]=dist\[1\]\[2\]+dist\[2\]\[4\]=8;
> 
> k=3,dist\[1\]\[4\]=dist\[1\]\[3\]+dist\[3\]\[4\]=7;
> 
> k=4,不变；
> 
> 最后每两个点距离都是最短距离。

### 六.一些题目 ###

##### 题1：信使 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70_pic_center 1]

1.  分析：
    
    我们可以把指挥部和哨所抽象为点，哨所与指挥部或者与哨所之间送信的时间看成两个点之间的边权。
    
    题目要我们求出**完成整个送信过程最短需要的时间**，其中完成整个过程：要求指挥部也就是点1能到达其他哨所也也就是其它点。
    
    所以我们要求出最短送信时间只要求出点1到其他点的最长时间即可，即**求出每个点到点1的最短距离的最大值**。
2.  选择算法：可以看出本题数据不大，因此可以选择最简单的floyd算法
3.  代码实现：

#include <iostream>
    #include <cstring>
    using namespace std;
    const int =110;
    int g[N][N],INF=0x3f3f3f3f;//用邻接矩阵存储边
    int n,m;
    
    int main()
    {
        cin>>n>>m;
        memset(g,0x3f,sizeof g);
        while(m--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            g[a][b]=g[b][a]=min(g[a][b],c);//题目给定的是无向边
        }
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
        }//floyd算法
        int res=0;
        for(int i=2;i<=n;i++)
        {
            if(g[1][i]==INF) //如果有哨所到不了，则输出-1
            {
                cout<<-1;
                return 0;
            }
            res=max(res,g[1][i]);//取所有点到源点最短距离的最大值即是题目所求
        }
        cout<<res;
    }

##### 题2：香甜的黄油 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70_pic_center 2]

1.  分析：题目的意思就是要我们**找出一个点使得其他点到该点的最短距离之和最小**。把牧场当成图上的点，牧场间的道路为图上的边。所以只需要对每个点求一次对其他点的最短路既可以。
2.  选择算法：这里数据的范围我们可以选择spfa()算法时间复杂度一共为O(nm);
3.  代码实现：
    
        #include <bits/stdc++.h>
        using namespace std;
        const int N=810,M=3000,INF=0x3f3f3f3f;
        int h[N],e[M],ne[M],w[M],idx;
        int dist[N];
        bool st[N];
        int n,p,c;
        int id[N];//存储每个牛所在的牧场编号
        void add(int a,int b,int c)//存储每两个牧场的信息
        {
            e[idx]=b;
            ne[idx]=h[a];
            w[idx]=c;
            h[a]=idx++;
        }
        int spfa(int x)
        {
            memset(dist,0x3f,sizeof dist);
            dist[x]=0;
            queue<int> q;
            q.push(x);
            st[x]=true;
            
            while(q.size())
            {
                int t=q.front();
                q.pop();
                st[t]=false;
                
                for(int i=h[t];i!=-1;i=ne[i])
                {
                    int j=e[i];
                    if(dist[j]>dist[t]+w[i])
                    {
                        dist[j]=dist[t]+w[i];
                        if(!st[j])
                        {
                            st[j]=true;
                            q.push(j);
                        }
                    }
                }
            }
            int res=0;
            for(int i=1;i<=n;i++)
            {
                int j=id[i];
                if(dist[j]==INF) return INF;//该点不能到达所有点，回无穷大。
                res+=dist[j];
            }
            return res;
        }
        int main()
        {
            memset(h,-1,sizeof h);
            cin>>n>>p>>c;
            for(int i=1;i<=n;i++) cin>>id[i];
            while(c--)
            {
                int a,b,c;
                cin>>a>>b>>c;
                add(a,b,c);
                add(b,a,c);//无向边
            }
            int res=INF;
            for(int i=1;i<=p;i++) res=min(res,spfa(i));//对每个点求解到其他点最短距离的和，取最小值。
            cout<<res;
        }

##### 题3：最小花费 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70_pic_center 3]

1.  分析：本题我们可以把每个人当做图中的点，每两个人转账需要的手续费当作图中的边权，题目要求我们求出（人）点A转账到（人）点B使B有100元，A初始的最少需要多少钱？我们可以逆向思考，只需要**求出点B到点A最大距离之积res**即可，然后用100除以res即得到A最少需要的费用。
2.  选择算法：这里选择朴素版dijkstra算法演示，这里存边需要注意。
3.  代码实现：
    
        #include <bits/stdc++.h>
        using namespace std;
        const int N=2e3+10;
        
        double g[N][N]，dist[N];;//题目要求保留8位小数这里用double
        int n,m;
        int A,B;
        bool st[N];
        
        double dijkstra()
        {
            dist[A]=1;
            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;
                st[t]=true;
                for(int j=1;j<=n;j++)
                dist[j]=max(dist[j],dist[t]*g[t][j]);//求最大距离乘积把'+'改成'*'即可
            }
            return dist[B];
        }
        int main()
        {
            cin>>n>>m;
            while(m--)
            {
                int a,b,c;
                cin>>a>>b>>c;
                double z=(100.0-c)/100;//这里存入的边权用double题目给出的是扣除百分之几，我们存入的是减去扣除的还剩余的百分之几，便于计算。
                g[a][b]=g[b][a]=max(g[a][b],z);
            }
            cin>>A>>B;
            double res=dijkstra();
            printf("%.8lf",100/res);
        }

### 七.附录（四种解法模板，转载自[AcWing][]） ###

##### 1.朴素dijkstra算法 #####

//时间复杂是 O(n2+m), n 表示点数，m 表示边数
    
    int g[N][N];  // 存储每条边
    int dist[N];  // 存储1号点到每个点的最短距离
    bool st[N];   // 存储每个点的最短路是否已经确定
    
    // 求1号点到n号点的最短路，如果不存在则返回-1
    int dijkstra()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        for (int i = 0; i < n - 1; i ++ )
        {
            int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
            for (int j = 1; j <= n; j ++ )
                if (!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
    
            // 用t更新其他点的距离
            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];
    }

##### 2.堆优化版dijkstra #####

//时间复杂度 O(mlogn), n 表示点数，m 表示边数
    
    typedef pair<int, int> PII;
    
    int n;      // 点的数量
    int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
    int dist[N];        // 存储所有点到1号点的距离
    bool st[N];     // 存储每个点的最短距离是否已确定
    
    // 求1号点到n号点的最短距离，如果不存在，则返回-1
    int dijkstra()
    {
        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];
    }

##### 3.Bellman-Ford算法 #####

//时间复杂度 O(nm), n表示点数，m 表示边数
    
    int n, m;       // n表示点数，m表示边数
    int dist[N];        // dist[x]存储1到x的最短路距离
    
    struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
    {
        int a, b, w;
    }edges[M];
    
    // 求1到n的最短路距离，如果无法从1走到n，则返回-1。
    int bellman_ford()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j < m; j ++ )
            {
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                if (dist[b] > dist[a] + w)
                    dist[b] = dist[a] + w;
            }
        }
    
        if (dist[n] > 0x3f3f3f3f / 2) return -1;
        return dist[n];
    }。

##### 4.spfa 算法 #####

//时间复杂度 平均情况下 O(m)，最坏情况下 O(nm),n 表示点数,m 表示边数
    
    int n;      // 总点数
    int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
    int dist[N];        // 存储每个点到1号点的最短距离
    bool st[N];     // 存储每个点是否在队列中
    
    // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
    int spfa()
    {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
    
        queue<int> q;
        q.push(1);
        st[1] = true;
    
        while (q.size())
        {
            auto t = q.front();
            q.pop();
    
            st[t] = false;
    
            for (int i = h[t]; i != -1; i = ne[i])
            {
                int j = e[i];
                if (dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                    {
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    
        if (dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }

##### 5.floyd算法 #####

//时间复杂度是 O(n^3), n 表示点数
    //初始化：
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                if (i == j) d[i][j] = 0;
                else d[i][j] = INF;
    
    // 算法结束后，d[a][b]表示a到b的最短距离
    void floyd()
    {
        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]);
    }

> 本文参考：
> 
> 1.[AcWing][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210427131356323.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70#pic_center
[AcWing]: https://www.acwing.com/blog/content/405/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210427131412159.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[img-qYSZjAVp-1619500179595_file_C_Users_LLLBJ_AppData_Roaming_Typora_typora-user-images_image-20210426210903420.png_lastModify_1619486064]: https://img-blog.csdnimg.cn/20210427131416427.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[img-8qGjtnwv-1619500179598_C_Users_LLLBJ_AppData_Roaming_Typora_typora-user-images_image-20210426210903420.png]: https://img-blog.csdnimg.cn/20210427131431589.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210427131236978.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210427131258647.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210427131315960.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1OTY2NDQw,size_16,color_FFFFFF,t_70#pic_center