dijstra c++实现

https://www.bilibili.com/video/BV1zz4y1m7Nq/?spm_id_from=333.999.0.0&;vd_source=ee4f2554eda9915089c465f3a21398b7

代码实现

```

#include <iostream>
#include <vector>

using namespace std;
int main()
{
    int n,m;//节点数, 边数
    cin>>n>>m;
    vector<vector<int>> g;
    for(int i=0;i<m;i++)
    {
        int from,to,weight;
        cin>>from>>to>>weight;
        vector<int> edge;
        edge.emplace_back(from);
        edge.emplace_back(to);
        edge.emplace_back(weight);
        g.emplace_back(edge);
    }

    vector<int> a(n);//是否收录 0 未收录 1 收录
    vector<int> b(n,INT32_MAX);//从节点0开始，最短距离
    b[0]=0;
    vector<int> c(n,-1);//前面点
    while(true)
    {
        //检查是否全部被收录
        int flag=1;
        for(int i=0;i<a.size();i++)
        {
            if(a[i]!=1)
            {
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            break;
        }
        //在未收录的节点中找到距离最小的节点
        int min_idx=-1;
        int min_dist=INT32_MAX;
        for(int i=0;i<a.size();i++)
        {
            if(a[i]==0)
            {
               if(b[i]<min_dist)
               {
                    min_idx=i;
                    min_dist=b[i];
               }
            }
        }
        //将距离最小的节点收录
        a[min_idx]=1;
        //尝试更新这个节点相邻节点的距离,和前面点
        for(int i=0;i<g.size();i++)
        {
            if(g[i][0]==min_idx&&a[g[i][1]]!=1)
            {
                int dist=b[min_idx]+g[i][2];
                if(b[g[i][1]]>dist)
                {
                    b[g[i][1]]=dist;
                    c[g[i][1]]=min_idx;
                }
                
            }
        }
    }
    cout<<endl;
    //输出结果
    for(int i=0;i<b.size();i++)
    {
        cout<<i<<": "<<b[i]<<endl;
        cout<<i;
        int last=c[i];
        while(last!=-1)
        {
            cout<<"<-"<<last;
            last=c[last];
        }
        cout<<endl;
    }
    return 0;
}

```

数据(和视频中一样)

```

9 28
0 1 4
1 0 4
0 7 8
7 0 8
1 2 8
2 1 8
1 7 11
7 1 11
7 8 7
8 7 7
7 6 1
6 7 1
2 8 2
8 2 2
8 6 6
6 8 6
2 3 7
3 2 7
2 5 4
5 2 4
6 5 2
5 6 2
3 5 14
5 3 14
3 4 9
4 3 9
5 4 10
4 5 10

```