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?
上一篇: Python装饰器 百日筑基之得气
下一篇: 前端常见的设计模式