图论-多源汇最短路问题

朴素版Dijkstra

• 利用到起点距离最短的点去更新其他点到起点的距离，迭代n-1次即可,复杂度O(n^2)
• 可以解决自环，重边的情况
• 边的权值不能为负数

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
const int N=505;
int a[N][N];//邻接矩阵
int n,m;
int dist[N];//1到i的最短距离
bool st[N];//判断该点是否已经用于松弛其它点
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int ts=1;ts<=n-1;ts++)//迭代n-1次
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[j]<dist[t]))
            t=j;
        }

        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],dist[t]+a[t][j]);
        }
        st[t]=true;
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof a);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=min(a[x][y],z);
    }
    int res=dijkstra();
    printf("%d\\n",res);

}

堆优化版的Dijkstra

• 复杂度$O(nlogn)$
• 用堆找到目前距离原点最短的点，然后用该点去松弛其它点，将所有更新点加进堆（有冗余情况，但方便比较。。）

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef pair<int,int> pii;
const int N=150005;
int h[N],ne[N],e[N],w[N],idx;
bool st[N];
int dist[N];
int n,m;
void add(int x,int y,int z)
{
    e[idx]=y,ne[idx]=h[x],w[idx]=z,h[x]=idx++;
}
int dijkstra()
{
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    memset(dist,0x3f,sizeof dist);

    dist[1]=0;
    heap.push({0,1});
    while(!heap.empty())
    {
        auto o=heap.top();
        heap.pop();

        if(st[o.second]) continue;//已经用该点松弛过 
        else st[o.second]=true;

        for(int i=h[o.second];~i;i=ne[i])
        {
            int j=e[i];

            if(dist[o.second]+w[i]<dist[j])
            {
                dist[j]=dist[o.second]+w[i];
                heap.push({dist[j],j});
            }
        }
    }

    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}
int main()
{
    memset(h,-1,sizeof h);

    scanf("%d%d",&n,&m);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    int res=dijkstra();

    printf("%d\n",res);
}

Kruskal

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int N=100005,M=200005;
int n,m;
int p[N];
struct lwy
{
    int u,v,w;
}a[M];
bool cmp(struct lwy q,struct lwy w)
{
    return q.w<w.w;
}
int find(int u)
{
    if(p[u]!=u) p[u]=find(p[u]);

    return p[u];
}
int main()
{
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }

    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        a[i]={u,v,w};
    }

    sort(a+1,a+1+m,cmp);
    int res=0;
    int num=0;
    for(int i=1;i<=m;i++)
    {
        int p1=find(a[i].u);
        int p2=find(a[i].v);
        if(p1!=p2)
        {
            p[p1]=p2;
            res+=a[i].w;
            num++;
        }
    }
    if(num!=n-1) puts("impossible");
    else printf("%d\n",res);
}

Floyd

(y总真言，简单易懂)

• f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么$。f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。$
  因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层。
• 读入邻接矩阵，将次通过动态规划装换成从i到j的最短距离矩阵
• 下面代码中，判断从a到b是否是无穷大距离时，需要进行if(t > INF/2)判断，而并非是if(t == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值（负数）而受到影响，t大于某个与INF相同数量级的数即可

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int N=205;
int a[N][N];
int dist[N][N];
int n,m,Q;
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) dist[i][j]=0;
            else dist[i][j]=INF;
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        dist[x][y]=min(dist[x][y],z);
    }

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dist[i][k]!=INF&&dist[k][j]!=INF)
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

    while(Q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(dist[x][y]==INF) puts("impossible");
        else printf("%d\n",dist[x][y]);
    }
}