Solution: Dijkstra (大概读作：迪杰斯特拉？求起点s到图中所有点的最短路径（单源最短路。vis[i]表示此点是否已被标记确定为最短。对dis数组进行维护，加快获取最小值以及执行一条边的扩展与更新。priority_queue< pa

int dep[MAXN + 5], fa[MAXN + 5][20 + 1];

if//如果这条边的终点到源点的距离大于起点到源点距离，就替换。中间关于“k”的部分，只是一种优化，可以删去，不影响算法。所以需要一个vis数组进行判断是否在队列中。

今天所说的就是常用的解决最短路径问题最后一个算法，这个算法同样是求连通图中单源点到其他结点的最短路径，功能和Bellman-Ford算法大致相同，可以求有负权的边的图，但不能出现负回路。但是SPFA算法的时间复杂度是O，k是常数，平均值为2，E是边数。我们

Dijkstra 算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。该算法的时间复杂度是O，相比于处理无负权的图时，比Bellmad-Ford算法效率更高。所谓松弛操作，简单的说就是更新两点间的最短距离。

由于二模和生物地理两门高考的临近，时间比较仓促，所以暂时跳过图论的(一)和(二)，即图的储存和遍历。从最短路径算法学起，首先要学习的是Floyed-Warshall算法。Floyed算法，是最简单也是最基础的最短路径算法，可以计算图中任意两点间的最短路径。

图论算法-Tarjan模板 为小伙伴们总结的Tarjan三大算法Tarjan缩点int n;

const int inf=1e9;int n,m,s,t;struct node{int v,cap;};vector<node> map[100010];int flow[10010][10010];int a[100010];int pr

4 using namespace std;5 queue<int>q;6 int map[1001][1001];7 int vis[1001];8 int n,m;11 q.push(p);12 vis[p]=1;13