题目描述

堆优化
（1）手写堆：时刻保证堆中有n个数
（2）优先队列：每次修改都往堆中插入一个数，可能有m个数（O(mlogm)）可能会有冗余数据，所以要加判断

稀疏图:用邻接表（不需要考虑重边）

for i:1~n 迭代n次，更新n次，则时间复杂度为O(n^2)
{
   t(找到不在s中的距离最近的点)   O（1）n次

   将点t加入到s中  （n次）

   t来更新所有点的距离（从t出来的所有的边能不能更新所有点的距离）（t到起点的距离能否更新当前点到起点（1号点的）直接的距离）即：判断dist[x]>dist[t]+w  （m次，m为该点边的数量）修改：mlogn
}

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N=150010;

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 dijstra()
{
    memset(dist,0x3f,sizeof(dist));

    dist[1]=0;

    priority_queue<PII,vector<PII>,greater<PII>> heap;    //只有m个数（m条边）

    heap.push({0,1});   //放入1号点，距离是0，编号是1

    while(heap.size())
    {
        auto t=heap.top();   //找到当前距离最短的点
        heap.pop();

        int ver=t.second;  //ver表示编号
        int distance=t.first;   //表示距离

        if(st[ver]) continue;   //如果这个点之前已经找过，则跳过这个点

        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])  //执行总数为m
        {
            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;   // memset是按字节赋值，一个int是32位4字节，所以有四个3f
    return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    int t=dijstra();

    cout<<t<<endl;

    return 0;
}