第三章 搜索与图论（二）

![[Pasted image 20240213110207.png]]
![[Pasted image 20240213115501.png]]
最短路问题一般分为 1. 单源最短路：一般来说是求一个点到其他所有点的最短距离（一个起点到....）
例子：一号点到 N 号点的最短路径（求出来一号点到其他所有点的最短路之后，显然一号点到 N 号点的最短路就求出来了）
可以分成两大类： 1. 第一类是所有边权都是正数 1. 朴素 Dijkstra 算法 O (n^2) n 指点数 m 表示边数：基于贪心 最好稠密图用（边特别多） 2. 堆优化版 Dijkstra 算法 O (mlogn) 稀疏图用这个 2. 存在负权边，某些边的权重可能都是负数
1.Bellman-Ford O (nm)
2.SPFA 一般 O (m)，最坏 O (nm) 一般效率比 bellman-Ford 要高的 2. 多源汇最短路：源点就是起点，汇点一般来说就是终点
例子：任选两个点，从其中一个点走到另外一个点的最短距离（起点和终点都是不确定的）（很多不同起点到....）
Floyd 算法 O (n^3)：基于动态规划

最短路难点在建图：指原问题抽象出来最短路问题 而不是原理
讲最短路问题的时候只用讲有向图的算法就可以了，因为无向图是一种特殊的有向图连两次就行
存储的区别：稠密图用邻接矩阵，稀疏图用邻接表

![[Pasted image 20240216103313.png]]
堆优化其实是和原朴素 Dijkstra 一个级别的，所以直接写 mlogn 就行了反正都差不多
堆优化中堆不必手写，使用优先队列即可，python 中用 set
但优先队列有可能有冗余，即：1 个点存了个 10 的距离又存了个 15 的距离
所以解决方法是，找到了之前确定过的直接 continue 扔掉就可以了

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair <int, int> PII;

const int N = 150010;
// 把N改为150010就能ac

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c){
    e[idx] = b,
    w[idx] = c,
    ne[idx] = h[a],
    h[a] = idx++;
}

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    // vector 指一维数组来实现
    heap.push({0, 1});
    
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = true; 
        
        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
        
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // g[a][b] = min(g[a][b], c);
        add(a, b, c);
    }
    
    int t = dijkstra();

    printf("%d\n", t);
    
    return 0;
}