dijkstra （好像有问题）

单源最短路，原理比较简单，就是贪心。每次选取最近的边（没选过），用它去更新其他的。传统做法是每次扫一遍寻找最近的遍，其实可以用堆优化。

void dijkstra(int s) {
  q.push(JCY{s, 0});
  for (int i = 1; i <= n + n; i++) {
    num[i] = 0x3f3f3f3f; //有因为最短路
  }
  num[s] = 0;//自己到自己是0
  while (q.size()) {
    JCY p = q.top();
    q.pop();
    if (vis[p.id]) { //选过了
      continue; // 不要
    }
    vis[p.id] = 1; // 标为选过
    for (int j = h[p.id]; j; j = ne[j]) {
      int v = e[j];
      if (num[v] > num[p.id] + w[j]) { //如果能更新
        num[v] = num[p.id] + w[j];
        q.push(JCY{v, num[v]}); //可以对其他人有贡献
      }
    }
  }
}

因为每个点都会进队列 \(O(n)\)，然后每次更新 \(O(m)\)，堆 \(O(log)\)，总共 \(O((n + m)log n)\)

spfa

类似于广搜，选择一个点，然后进行更新

void spfa() {
  for (int i = 1; i <= n; i++) {
    num[i] = 0x3f3f3f3f; //不说
  }
  num[s] = 0;
  vis[s] = 1; //是否在队列里
  q.push(s);
  while (q.size()) {
    int u = q.front(), v;
    q.pop();
    vis[u] = 0;
    for (int i = h[u]; i; i = ne[i]) {
      v = e[i];
      if (num[v] > num[u] + w[i]) { //松弛
        num[v] = num[u] + w[i];
        if (!vis[v]) { //不在队列
          q.push(v);//进队
          vis[v] = 1;
        }
      }
    }
  }
}

还一个晚点写(鸽了好久，不想管了呢)

JZTXT

最短路

dijkstra （好像有问题）

spfa