Dijkstra（迪杰斯特拉算法）

在给定不带负权的有向图中，求两点间的最短路（无向图可以看成特殊的有向图）

朴素版的dijkstra算法 ( O ( n 2 ) ) (O(n^2)) (O(n2))

int arr[510][510], dis[510], flag[510];

arr是稀疏矩阵存图，最开始把所有的值设置为正无穷，
一般是稠密图—稀疏矩阵来存
步骤如下：
1、初始化距离数组dist，dist[1]=0，因为第一个点到第一个点的距离为 0，第一步只有起点被遍历到了。其他的点 i 初始化为正无穷，一般用较大的数字，比如dis[i]=0x3f3f3f3f
2.1:有 n 个点，遍历 n 次（ s 为当前已知确定最短距离的集合）
2.2:找到不在集合s中的距离最近的点t
2.3:把t加到集合s中
2.4：用t更新其他点的距离
预处理arr数组，先初始化为正无穷。因为有重边，所以每条边要取最小的那个：

int main()
{
    memset(arr, 0x3f, sizeof(arr));
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &x, &y, &z);
        arr[x][y] = min(arr[x][y], z);
    }
}

注意：
最开始不能加st[1]=true，因为我们是从第一个点开始算起走的，第一个点也要被算一次
如果不存在从1-n的最短路，那么dist[n]是正无穷：

int arr[510][510], dis[510], flag[510];
int n, m, x, y, z;

int dijkstra()
{
    memset(dis, 0x3f, sizeof(dis));//把距离初始化为最大值
    dis[1] = 0;
//    flag[1] = true;//不能加这句话
    for(int i = 1; i <= n; ++i)
    {
        int t = -1;
        for(int j = 1; j <= n; ++j)//找到目前最小距离的下标
            if(!flag[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
                
        flag[t] = true;//t这个点已经确定了，所以把它加入已知最短距离的点的集合
        
        for(int j = 1; j <= n; ++j)//更新相连的点的距离
            dis[j] = min(dis[j], dis[t] + arr[t][j]);
    }
    return dis[n] == INF ? -1 : dis[n];
}

dijkstra的堆优化 ( O ( m l o g n ) ) (O(mlogn)) (O(mlogn))

堆优化的题目一般用于点较多的题，比如有 1 e 6 1e6 1e6个点这种，如果朴素版的 d i j k s t r a dijkstra dijkstra就会超时

邻接表存图

这里多存了一个距离，注意w[idx]=c要放在h[a]=idx++前面，因为最后才更新 i d x idx idx

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

堆优化代码，用优先队列来做，代码模式跟BFS差不多

int dijkstra()//用优先队列优化
{
    memset(dis, 0x3f, sizeof(dis));//把距离初始化为最大值
    dis[1] = 0;
    priority_queue<PII,vector<PII>,greater<>>heap;
    heap.push({0,1});//前面是距离，后面是点
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int distance=t.first,point=t.second;
        if(flag[point])//如果这个点已经被处理过了就不需要再处理了
            continue;
        flag[point]=true;//此时的point一定是当前距离最小的点，直接加入已处理过的点的集合
        for(int i=h[point];i!=-1;i=ne[i])//这里的i就相当于idx
        {
            int j=e[i];
            if(dis[j]>distance+w[i])//因为这里的i相当于idx，所以可以用w[i]
            {
                dis[j]=distance+w[i];
                heap.push({dis[j],j});//注意是先存距离，再存点
            }
        }
    }
    return dis[n] == INF ? -1 : dis[n];
}