学习了四种算法，分别是SPFA Dijkstra Kruskal Prim。还有拓扑排序。周日周一打了几个板子题目，周二写完了洛谷上的题目，周三周四瞎找了两道题目做了，还有一道没做出来
前面还知道基本原理，到了后面做题时就是胡乱bfs带一个优化了。结果周四晚自习的时候突然发觉自己什么都不会。连板子都不会写了，胡乱复习了一下Dijkstra和Kruskal。结果题目异常坑爹，A,B都只能用spfa，听后面学长小声说，大概是去掉priority_queue改成queue。我这周倒是做过一题朴素的，但那时是prim。后来瞎搞了过了A,B。运气很不错。
-----------------------------------
SPFA
SPFA在于不断松弛，松弛后的解状态改变了，所以为了 得到它引申出去的各种各样的最优解，需要重新走一遍流程。
由于是面向节点的，需要知道是哪个节点，以及节点对应的“长度，价值，费用……”，一旦有更优解，就把更优解拉进队伍里，同时更新这个解的状态。
Dijkstra
可以理解为Priority_queue版的SPFA，多了一个vis数组，在循环里就是一个节点只走一边流程。理由是，对于节点A，有可能走多次流程的话，那么A（此时是个strruct，里面还存着这个节点的路径）{x，wmin}一定会排在最前面，又因为Dijkstra是不断扩展路径，也就是已有点集和外部点集的（交互？），那么不存在这个节点被处理后，又蹦跶出一条新的更优的通向这个节点的路径。
这几天碰到的问题就比如，最长路径为什么不可以用
-----------------------------------
A - 一个人的旅行
虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。
---------------
明天下午社会实践逃不掉，计算机导论没写，学生手册没考，四级准考证没打印。头疼(物理，先放这吧。
原文：https://www.cnblogs.com/asanagiyantia/p/12032356.html