Dijkstra学习笔记

暂时空白....

没有前置，我用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?

知道为什么RE了，之前的没加vis[now]=true;，真是令人生艹

巴特西

Dijkstra学习笔记

最新文章

热门文章