欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Dijkstra学习笔记

程序员文章站 2022-03-20 20:01:52
~~暂时空白....~~ 没有前置,我用vector存图 cpp //存储 struct edge{ int w,to;//w是权值,to是连接到的下一条边 }; vector e; //连边 ... for(int i=1;i ......

暂时空白....
没有前置,我用vector存图

//存储
struct edge{
    int w,to;//w是权值,to是连接到的下一条边
};
vector<edge> e;
//连边
...
for(int i=1;i<=m;i++)
{
    int to,s,w;
    scanf("%d%d%d",&s,&to,&w);
    edge tmp;
    tmp.to=to,tmp.w=w;
    e[s].push_back(tmp);//有向图
    tmp.to=s;
    e[to].push_back(tmp);//无向图
}

每一次用选取当前数组中dis中存储的最小值的点,如果没有访问过,就可以访问,

...
    for(int i=1;i<=n;i++)
    {
        int min=0x3f,now;
        for(int j=1;j<=n;j++)
        {
            if(vis[j]==0&&dis[j]<min)
            {
                min=dis[j];
                now=j;
            }
        }
        vis[now]=1;

并更新周围的点

        for(int j=0;j<e[now].size();j++)
        {
            dis[e[now][j].to]=max(dis[now]+e[now][j].w,dis[e[now][j].to]);
            if(dis[now]+e[now][j].w<dis[e[now][j].to])
            {
                dis[e[now][j].to]=dis[now]+e[now][j].w;
            }
        }
    }

应该写对了吧....因为我爆掉了qwq,而且似乎是re?