| Dijkstra求最短路径&例题 | 您所在的位置：网站首页 › dijkstra最短路径例题 › Dijkstra求最短路径&例题 |
|
讲了半天好像也许maybe听懂了一点，先写下来233 先整理整理怎么存（开始绕） 最简单的是邻接矩阵存，但是开到10000*10000就MLE了,所以我们用链式前向星存（据说是叫这个名字吧） 这是个什么鬼玩意呢？ 我们在记录时，以输入的顺序记录。 我们记录一条边，就记下它的终点(to)，权值（就是边长）(dis)，以及和这条边的起点相同，编号稍微小一点的边的编号(next)（开始绕） 这里我们记录当前每个点的所有出边（就是起点是这个点的边）中编号最大的那一条边（因为上面的next是编号稍微小的边） 当然也可以依据自己的习惯存储边 先上段代码 int head[nmax],n,m,s;//head[i] 是 以 点 i 为 起 点 ， 所 有 出 边 中 编 号 最 大 的 一 个 priority_queue q; void add(int fr,int _to,int _dis) { cnt++; eage[cnt].to=_to; eage[cnt].dis=_dis; eage[cnt].next=head[fr];//fr 为 from 的 简 写 , 这 里 的 以 点 i 为 起 点 的 边 多 了 一 条， //所 以 上 一 个 以 点 i 为 起 点 的 编 号 最 大 的 边 就 是 这 里 的 以 i 为 起 点 编 号 最 大 的 边 的 上 一 条 边 head[fr]=cnt; //更 新 head[i] }Edge [50001]; const int inf=2147483647; int main() { scanf("%d%d%d",&n,&m,&o_node); dis[o_node]=0; for(int i=1;i |
| CopyRight 2018-2019 实验室设备网 版权所有 |