1018 Public Bike Management (30) Dijkstra算法 + DFS

题目及题解

https://blog.csdn.net/CV_Jason/article/details/81385228

迪杰斯特拉重新认识

两个核心的存储结构：

int dis[n]；　　//记录每个点到源头的最短距离

bool mark[n];　　//标记每个顶点到

/*如果想要保存路径，创建一个二维数组，或者vector【n】，

里面的每个一维数组表示到达该节点的前一个节点，在(u为当前选出的新节点）当dis[v]==dis[u]+e[u][v],说明通过u到达v的路径也是最短路径，于是把u加入vector【v】；

如果(u为当前选出的新节点）当dis[v]>dis[u]+e[u][v],则说明有更短的路径，于是vector【v】.clean();清空vector【v】，然后加入u

这样任意一点x，（像遍历树一样）只使用dfs/bfs就能把所有从x到源的路径求出；

一个核心公式：

e[a][b]+dis[b]<e[a];　　//当通新加入的节点b到达a的路程，比已知的到a的路程短，则把dis[a]更新为e[a][b]+dis[b];

流程：

初始化：

dis 设置成inf 　　　　//自定义无穷

mark 设置成false　　　　

dis[0]设置成0　　　　　　//0可换成任意一点源

执行核心过程：

for（n次，每次加入一个点）

{　　设置两个变量记录每次找的最小的点的下标和距离

　　for（n次，找一个未加入的点）

　　{　　当if（mark【i】==false&&dis【i】<minDis）则更新下标和当前发现的最小距离}

　　for（n次，检查是否能用新的点更新原来dis【n】）

　　{}

}

深度优先复习

外界 stack/vector

dfs（x）

{　　s或v push（x）

　　if（x为最深一层）

　　{一系列的处理操作}

　　for（能从x往下走的路）

　　{ dfx（x+/-1） }

　　s或v pop；//回溯到没有上一层的x，继续执行上一层for（x的下一条路）的

}

巴特西