训练日记1.2

松弛操作：

基本可以理解为以下代码:

if(dist[j]>dist[t]+w)

        dist[j]=dist[t]+w;

dijkstra算法： dijkstra算法适用于边权为正值的最短路问题，是解决图论问题时经常使用的算法，一般只能用于解决单源最短路问题（并且要求所以边权值均为正数），即从单个源点出发到所有节点的最短路。另外该算法同时适用于有向图和无向图。一般有两种实现方式，一种是邻接矩阵实现（朴素dijkstra算法），另一种是用c++自带的stl的堆优化即优先队列实现（堆优化dijkstra算法)。两种方法有各自的适用条件，例子如下，以下例题来源于acwing。

朴素dijkstra算法：适用于稠密图即m≈n^2时的情况，o（n^2)。

利用邻接矩阵来实现图的存储

原题来源：acwing：849

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 nn 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m

接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n≤500
1≤m≤105
图中涉及边长均不超过10000。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

基本思路：利用邻接矩阵来实现图的存储，

1：用dist[]数组表示距离，初始为无穷，d[1]初始为0；用bool标记该点的最短路是否算出，用t来更新当前的点，不断遍历寻找最小值。

#include 
using namespace std;
const int N=520;
int n,m;
int g[N][N],dist[N];
bool st[N];//布尔变量用于确认该点的最短路是否算出
//dijkstra算法模板
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);//将dist[]数组初始化为无穷大；
    dist[1]=0;//单源点到自身距离为1；
    for(int i=0;idist[t]+g[t][j])
                dist[j]=dist[t]+g[t][j];
         //遍历求起点到当前点的距离和从起点通过另一条路上的t到当前距离的更小值，若更小则更新数据。
            
        st[t]=true;//标记此点到起点的最短路一秋出；
        
    }
    if(dist[n]==0x3f3f3f3f) return -1;//若dist[n]的值为变，则说明从起点无法到达该点，返回-1；
    else return dist[n];//反之则直接返回dist[n]的值即为所求
    
    
    
}
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]=min(g[a][b],c);//考虑到可能存在重边情况，在求最短路是只需用到最小边权值即可
    }
    cout< 
 
堆优化版dijkstra算法：适用于稀疏图，即n≈m，o(m*logn) 
题目来源：acwing850；
 
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
 
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
 
输入格式
 
第一行包含整数 n 和 m。
 
接下来 mm 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
 
输出格式
 
输出一个整数，表示 1 号点到 n号点的最短距离。
 
如果路径不存在，则输出 −1。
 
数据范围
 
1≤n,m≤1.5×10^5
 图中涉及边长均不小于 0，且不超过 10000
 数据保证：如果最短路存在，则最短路的长度不超过 10^9
 
输入样例：
 
3 3
1 2 2
2 3 1
1 3 4
 
输出样例：
 
3
 
基本思路，利用优先队列来实现图的存储，根据题意不断遍历即可（缺点是队列可能会出现冗余，所以需要用布尔变量确定当前点是否被查询过）
 
​
#include 
using namespace std;
const int N=2e5+10;
typedef pairPII;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
//add函数是利用邻接表实现对图的存储，
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
   
}
//堆优化（优先队列）dijkstra算法模板
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue, greater> heap;
    //priority_queue默认是大根堆，需要用第三个参数greater实现小根堆操作，
    heap.push({0,1});
    while(heap.size())
    {
        auto  t=heap.top();//每次找到起点到该点距离最小的点即队头
        heap.pop();
        int ver=t.second,disance=t.first;//ver表示当前查询元素编号，distance表示距离。
        if(st[ver]) continue;//堆优化可能会出现冗余情况，若该点的最短路已经确定，那么跳出当前循环。
        st[ver]=true;//标记当前点已被查询过。
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[ver]+w[i])
            {
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
        
        
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
   
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout< 

bellman_man算法： 
一般用于解决单源最短路中存在负权边的情况并且有边数限制的最短路问题，一般为 
ellman—Ford算法的核心：对每一条边都进行松弛操作 
每次松弛操作实际上是对相邻节点的访问(相当于广度优先搜索)，第n次松弛操作保证了所有深度为n的路径最短。 
O(n*m)； 
例题来源acwing853；
 
  
 
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
 
请你求出从 1 号点到 nn 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
 
注意：图中可能 存在负权回路 。
 
输入格式
 
第一行包含三个整数 n,m,k。
 
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 yy的有向边，边长为 z。
 
输出格式
 
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
 
如果不存在满足条件的路径，则输出 impossible。
 
数据范围
 
1≤n,k≤500
 1≤m≤10000
 任意边长的绝对值不超过 10000
 
输入样例：
 
3 3 1
1 2 1
2 3 1
1 3 3
 
输出样例：
 
3
 
     在bellman_ford算法中对图的存储方式多样，可以用结构体，邻接表，邻接矩阵存储，下面介绍利用结构体存储图的方式。对于每次求最短路都需要迭代k次，利用暴力搜索实现最短路的求取。
 
#include 
using namespace std;
const int N=520,M=1e4+10;
int n,m,k;
int dist[N],backup[N];
//结构体实现对图的存储。
struct  edge{
    int a,b,w;
}edges[M];

int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i0x3f3f3f3f/2) puts("impossible");
    else cout< 
  
 
spfa算法: 
一般适用于单源最短路中存在负权边的情况，一般优于bellman_man算法，需要特别注意的是，图中不能出现负环。并且可以判断是否图中是否存在负环。 
以下例题来源acwing851：
 
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
 
请你求出 1 号点到 n 号点的最短距离，如果无法从 1号点走到 n 号点，则输出 impossible。
 
数据保证不存在负权回路。
 
输入格式
 
第一行包含整数 n 和 m。
 
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
 
输出格式
 
输出一个整数，表示 1 号点到 n 号点的最短距离。
 
如果路径不存在，则输出 impossible。
 
数据范围
 
1≤n,m≤10^5
 图中涉及边长绝对值均不超过 10000
 
3 3
1 2 5
2 3 -3
1 3 4
 
输出样例：
 
2
 
基本思路：利用邻接表来实现对图的存储，利用队列实现对bellman_ford算法的优化。
 
#include 
using namespace std;
const int N=1e5+10;
int n,m;
int dist[N],e[N],h[N],ne[N],idx,w[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 spfa()
{
    queueq;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    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])
                {
                    q.push(j);
                    st[j]=true;
                }
                
            }
        }
    }
    
    
    
};

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        
    }
    spfa();
    if(dist[n]==0x3f3f3f3f) puts("impossible");
    else cout< 
判断负环:判断
 
 
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
 
请你判断图中是否存在负权回路。
 
输入格式
 
第一行包含整数 n和 m。
 
接下来 mm 行每行包含三个整数x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
 
输出格式
 
如果图中存在负权回路，则输出 Yes，否则输出 No。
 
数据范围
 
1≤n≤2000
 1≤m≤10000
 图中涉及边长绝对值均不超过 10000
 
3 3
1 2 -1
2 3 4
3 1 -4
 
输出样例：
 
Yes
 
 基本思路和spfa算法实现基本相同，加个cnt[]数组统计点数即可
 
#include 
using namespace std;
const int N=1e4+10;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N],cnt[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 spfa()
{
    queueq;
    for(int i=1;i<=n;i++)
    {
        st[i]=true;
        q.push(i);
    }
    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];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                //如果当前cnt[]中的点的数量已经多余n即存在负环，
                if(!st[j])
                {
                   
                    q.push(j);
                     st[j]=true;
                }
                
            }
        }
    }
    return false;
    
    
    
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
    
    
}
 
 
Floyd算法： 
一般用于多源汇最短路求解的情况，一般为O（n^3),
 
核心为三重循环：
 
for(int k=0;k 
        for(int i=0;i 
                for(int j=0;j 
                        d[i][j]=min(d[i][j],d[j][k]+d[k][j])
 
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
 
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x到点 y 的最短距离，如果路径不存在，则输出 impossible。
 
数据保证图中不存在负权回路。
 
输入格式
 
第一行包含三个整数 n,m,k
 
接下来 m 行，每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。
 
接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。
 
输出格式
 
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
 
数据范围
 
1≤n≤200
 1≤k≤n^2
 1≤m≤20000
 图中涉及边长绝对值均不超过 10000
 
输入样例：
 
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
 
输出样例：
 
impossible
1
 
基本思路:利用邻接矩阵来实现对图的存储，l
 
 
 
#include 
using namespace std;
const int N=210,INF=1e9;
int n,m,q;
int d[N][N];

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



int main()
{
    scanf("%d%d%d",&n,&m,&q);
    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;
        }
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b]=min(d[a][b],c);
    }
    floyd();
    while(q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(d[a][b]>INF/2) cout<<"impossible"< 
注：由于本人水平有限，上面所写可能会出现错误，忘不吝指正，本人十分感谢。