_最短路问题_分为单源最短路和多源汇最短路
1.单源最短路
    （1）所有边权都是正的
        a.点少（n小）
            朴素Dijkstra算法   O(n^2)
        b.点多（n大）
            堆优化版的Dijkstra算法    O(mlogm)
    （2）存在负权边
        a.存在负权回路
            Bellman-ford算法  O(n*m)
        b.不存在负权回路
            SPFA算法  一般O(m),最坏O(n*m)
                除了可以求单源最短路，还可以判断图中是否存在负环
2.多源汇最短路
    （1）不存在负权回路
        a.Floyd算法   O(n^3)

849. Dijkstra求最短路 I

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=510;
int g[N][N],n,m;
int dist[N];//dist[i]存储第i个点到源点（起点）的距离 
bool st[N];//第i个点到源点的最小路径是否已经确定
/*
整体思路及其步骤：
                （1）首先需要三个东西，邻接矩阵，一个dist[N]存储某个点到源点的距离，
                 还需要一个st[N]数组标记某个点是否已经确定最小距离
                 注意：邻接矩阵和dist数组都需要初始化为正无穷 
                （2）需要进行n-1次循环，然后再循环找到未被标记过的点并且这个点到源点的距离
                     小于用mark标记的点到源点的距离（其实这句话的意思也是：在未被标记的点中，
                     找到到源点距离最近的点，并用mark标记它的下标 
                （3） 遍历n个点，看源点到每个点的距离是否可以通过mark这个点缩短
                （4）更新mark的状态st 
*/ 
int Dijkstra()
{
    memset(dist,0x3f3f3f3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n-1;i++)
    {
        int mark=-1;
        for(int j=1;j<=n;j++)//找到距离源点最近的点mark 
        {
            if(!st[j]&&(mark==-1||dist[j]<dist[mark]))
                mark=j;
        }
        for(int j=1;j<=n;j++)//看看有没有点可以通过mark这个点缩短到源点的距离 
        {
            dist[j]=min(dist[j],dist[mark]+g[mark][j]);
        }
        st[mark]=true;
    }
    if(dist[n]==0x3f3f3f3f)
        return -1;
    return dist[n];
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(g,0x3f3f3f3f,sizeof g);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(c,g[a][b]);
    }
    cout<<Dijkstra();;
    return 0;
}

850. Dijkstra求最短路 II

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6;
int n,m,idx,head[N],e[N],w[N],ne[N];
int dist[N];
bool st[N];
/*
与朴素Dijkstra算法不同之处是：
                            （1）朴素的算法在获取与源点最小距离时是通过遍历每个点进行比较，
                                 改良之后的是用堆进行自动排序 
                            （2）图的存储方式不一样 
                            （3）朴素的mark标记的是下标，而这个是结点 
*/
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=head[a];
    head[a]=idx;
    idx++;
}
int Dijkstra()
{
    memset(dist,0x3f3f3f3f,sizeof dist);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});//把第一个点的dist[1]距离为0放进heap
    while(heap.size())
    {
        PII t=heap.top();//自动获取一个到源点最小距离的点 
        heap.pop();
        int distance=t.first,mark=t.second;
        if(st[mark])    
            continue;
        st[mark]=true;
        for(int i=head[mark];i!=-1;i=ne[i])//遍历与mark这个点相关联的点 
        {
            int j=e[i];
            if(dist[j]>dist[mark]+w[i]) 
            {
                dist[j]=dist[mark]+w[i];
                heap.push({dist[j],j});
            }
        }
    } 
    if(dist[n]==0x3f3f3f3f)
        return -1;
    return dist[n];
}
int main()
{
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout<<Dijkstra();
    return 0;
}

853. 有边数限制的最短路bellman-ford

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int n,m,k,dist[N],backup[N];
/*
    bellman_ford算法：
        (1)解决的问题是图中存在负权边时的单源最短路，也可以求在k条边限制下的单源最短路
        (2)需要准备三个东西：存储边的结构体数组，源点到汇点的距离dist[],与dist相同的backup
        (3)先给dist初始化，然后记得初始源点的dist[]
           循环k次，然后将dist赋值给backup
           循环m条边，判断b点能不能通过a点进行缩短
           判断dist[n]，但是并不是判等         
*/
struct Edge
{
    int a,b,c;
}edges[M];
void bellman_ford()
{
    memset(dist,0x3f3f3f3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(int i=0;i<m;i++)
        {
            int a=edges[i].a,b=edges[i].b,c=edges[i].c;
            dist[b]=min(dist[b],backup[a]+c);
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++)
    {
        int A,B,C;
        scanf("%d%d%d",&A,&B,&C);
        edges[i]={A,B,C};
    }
    bellman_ford();
    if(dist[n]>=0x3f3f3f3f/2)
        printf("impossible");
    else
        printf("%d",dist[n]);
    return 0;
}

851. spfa求最短路

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=100010;
int n,m,dist[N];
bool st[N];
int e[N],w[N],ne[N],head[N],idx;
/*
    spfa求最短路：
        (1)用邻接表存储
        (2)需要三个东西,dist[],queue,st[] (结点i在队列里面则被标记为真，出队就被标记为假) 
        (3)初始化dist为无穷，初始化dist[1]=0
        (4)如果队列不为空，那么一直循环；
           取出队头元素，如果这个队头元素可以将把之连接的点与源点的距离缩短
           则更新dist,如果与之连接的点未入队，则入队 
    spfa与Dijkstra主要不同：
        Dijkstra需要将dist排序，而spfa不需要 
*/
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=head[a];head[a]=idx;idx++;
}
void spfa()
{
    queue<int> q;
    memset(dist,0x3f3f3f3f,sizeof dist);
    dist[1]=0;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=head[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(head,-1,sizeof head);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    spfa();
    if(dist[n]==0x3f3f3f3f)
        printf("impossible");
    else
        printf("%d",dist[n]);
    return 0;
}

852. spfa判断负环

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=100010;
int n,m,dist[N],cnt[N];
bool st[N];
int e[N],w[N],ne[N],head[N],idx;
/*
    spfa与Dijkstra主要不同：
        Dijkstra需要将dist排序，而spfa不需要 
    spfa判断是否存在负环
        (1)不需要对dist进行任何的初始化 
        (2)只需要最开始把所有元素入队
        (3)增加一个cnt数组，在更新dist时，也更新cnt,若有任意一个cnt[i]大于等于点数，则存在负环
*/
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=head[a];head[a]=idx;idx++;
}
bool spfa()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=true;
    }
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=head[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;
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof head);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    if(spfa())
        printf("Yes");
    else
        printf("No");
    return 0;
}

854. Floyd求最短路

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=210,INF=1e9+10;
int n,m,q,d[N][N];
/*
    Floyd算法：
    (1)求的是任意一个点到任意另一个点的最短路
    (2)用二维矩阵存储图，也在这个二维矩阵上更新点到点的最短距离
    (3)三层循环，第一层是循环经过的点k，第二层是循环起始点i，第三层是循环重点j
       看看能不能通过k点缩短i与j的距离
       d[i][j]=min(d[i][j],d[i][k]+d[k][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]);
            }
        }
    }
}
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;
        }
    }
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b]=min(c,d[a][b]);
    }
    Floyd();
    while(q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(d[a][b]>=INF/2)
            puts("impossible");
        else
            printf("%d\n",d[a][b]);
    }
    return 0;
}

_存储方式的对比_
（1）邻接矩阵
    a.朴素Dijkstra
    b.Folyd
（2）邻接表
    a.堆优化版的Dijkstra
    b.spfa
（3）结构体
    a.bellman-ford

需要排序的算法：Dijkstra算法

用到队列的算法：
(1)堆优化版的Dijkstra用到优先队列模拟堆
(2)spaf算法用到队列