今天学习了最短路 ， 来总结一下

最短路

1. $dijkstra$ 算法，用于没有负权边的图
2. $spfa$ 算法，用于有负权边，但没负环的图
3. $bellman-ford$ 算法，用于有负权环的图，一般有边数限制

T1 Dijkstra求最短路 II

solution

$dijkstra$ 算法 过程

1. 准备步骤 ： $vis$ 数组，判断是否遍历过；$dis$ 数组，存从起点到每一个点的距离；$q$ 优先队列，快速找最小值
2. 初始化 $dis[i] = 0$，其余节点的值为 $inf$
3. 将 $q$ 的堆顶 $x$ 取到，弹出 $x$，此时 $x$ 为 $dis$ 值最少，注意如果 $x$ 被标记要 $continue$
4. 从 $x$ 出发，遍历 $x$ 的所有子节点，若 $dis[y] > dis[x] + w$，则使用 $dis[x]$ 更新 $dis[y]$ 这一步叫做松弛，如果 $y$ 还没有被标记，入队且标记，否者不管

时间复杂度 ： $O((n + m)logn)$，朴素算法：$O(n^2)$

code

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f;

struct node{
  int x , w;
  
  bool operator <(const node &a) const &{
    return a.w < w;
  }
};

int n , m , s , dis[N] , vis[N];
vector<node> g[N];

void dijkstra(node s){
  priority_queue<node> q;
  q.push(s);
  memset(dis , inf , sizeof(dis));
  dis[s.x] = 0;
  
  while(!q.empty()){
    node t = q.top();
    q.pop();
    if(vis[t.x]) continue;
    vis[t.x] = 1;
    for(int i = 0 ; i < g[t.x].size() ; i ++){
      node k = g[t.x][i];
      if(dis[k.x] > dis[t.x] + k.w){
        dis[k.x] = dis[t.x] + k.w;
        if(!vis[k.x]) q.push({k.x , dis[k.x]});
      }
    }
  }
  if(dis[n] == 0x3f3f3f3f) cout << -1;
  else cout << dis[n];
}

int main(){
  cin >> n >> m;
  
  for(int i = 1 ; i <= m ; i ++){
    int x , y , w;
    cin >> x >> y >> w;
    g[x].push_back({y , w});
  }
  dijkstra({1 , 0});
  return 0;
}

注意如果用得结构体的话要重载 $<$ 运算，因为小根堆是用的 $<$