1.dijkstra

时间复杂度：O(n^2)

n次迭代，每次找到距离集合S最短的点

每次迭代要用找到的点t来更新其他点到S的最短距离。

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=510;

int g[N][N];

int dis[N],n,m;//dis[i]表示节点i到初始点的最短距离

bool st[N];

int dijkstra()

{

    memset(dis,0x3f,sizeof dis);

    dis[1]=0;

    //st[S]=1;如果在迭代之前，将起点放入S数组后，24行，一直无法找到距离S的最近节点。

    //相反27行直接判断st[t]=true,可以找到第一个节点，并一直进行下去。

    for(int i=1;i<=n;i++)//n次迭代，没次找到距离集合S的最短的点

    {

        int t=-1;

        for(int j=1;j<=n;j++)

        {

            if(!st[j]&&(t==-1||dis[j]<dis[t]))

            {

                t=j;

            }

        }

        st[t]=1;//这是第一个节点。

        //找到节点t是距离集合S的最短距离的点之后

        //用t来更新其他点到s的距离

        for(int j=i;j<=n;j++)

        {

            dis[j]=min(dis[j],dis[t]+g[t][j]);

        }

    }

    if(dis[n]==0x3f3f3f3f)return -1;

    else

        return dis[n];

}

int main()

{

    memset(g,0x3f,sizeof g);

    /*

    初始化成0会比较好，但不初始化也没关系。因为题目中说所有边权都是正的，

    所以 dist[i] + g[i][i] 一定大于 dist[i]，所以i->i这条边一定不会被用到。

    */

    cin>>n>>m;

    for(int i=0;i<m;i++)

    {

        int a,b,c;

        cin>>a>>b>>c;

        g[a][b]=min(g[a][b],c);

    }

    cout<<dijkstra()<<endl;

    return 0;

}

2.堆优化版dijkstra

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

typedef pair<int,int>PII;

#define ff first

#define ss second

const int N=2e5+10;

int dis[N],n,m,idx,h[N],ne[N],e[N],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 dijkstra()

{

    memset(dis,0x3f,sizeof dis);

    dis[1]=0;

    priority_queue<PII,vector<PII>,greater<PII>>heap;

    heap.push({0,1});

    while(heap.size())

    {

        auto t=heap.top();

        heap.pop();

        int dist=t.ff,indx=t.ss;

        if(st[indx])continue;

        st[indx]=1;

        for(int i=h[indx];~i;i=ne[i])//用找到的距离集合S最近的点来更新其他点到集合S的距离

        {

            int j=e[i];

            if(dis[j]>dis[indx]+w[i])

            {

                dis[j]=dis[indx]+w[i];

                heap.push({dis[j],j});

            }

        }

    }

    if(dis[n]==0x3f3f3f3f)return -1;

    else

    return dis[n];

}

int main()

{

    memset(h,-1,sizeof h);

    cin>>n>>m;

    while(m--)

    {

        int a,b,c;

        cin>>a>>b>>c;

        add(a,b,c);

    }

    cout<<dijkstra();

}

2.prim

时间复杂度：O(n^2)

同dijkstra算法

#include<iostream>

#include<cstring>

#include<algorithm>

//稠密图

using namespace std;

const int N=510,M=1e5+10;

//Prim算法给出最小生成树的权重和

int g[N][N],dis[N];

//dis[i]表示第i个点到已经纳入最小生成树集合S的最小距离

int n,m,res;

bool st[N];

int prim()

{

    memset(dis,0x3f,sizeof dis);

    for(int i=0;i<n;i++)

    {

        int t=-1;//那个点是哪个点？

        for(int j=1;j<=n;j++)//在n个点中寻找不到集合S中距离

        //S最近的点的标号

        {

            if(!st[j]&&(t==-1||dis[j]<dis[t]))

                t=j;

        }

        //找到了那个点t

        st[t]=1;

        //中间关于i==0时的几个判断

        //cout<<dis[t]<<endl;

        if(i)

        {

            res+=dis[t];

            //cout<<res<<endl;

        }

        //在n次迭代中的判断，如果该图是一个不连通图，不存在最小生成树

        if(i&&dis[t]==0x3f3f3f3f)return 0x3f3f3f;

        //用t点来更新其他点到S的距离

        for(int j=1;j<=n;j++)

            dis[j]=min(dis[j],g[t][j]);

    }

    return res;

}

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

    }

    int t=prim();

    if(t==0x3f3f3f)

        cout<<"impossible"<<endl;

    else

        cout<<t;

    return 0;

}