Dijkstra学习笔记

佚名 6年前 (2019-04-09) 随笔 1163人围观抢沙发百度已收录

暂时空白....
没有前置，我用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中存储的最小值的点，如果没有访问过，就可以访问，

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

...
    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?