搜索与图论 Dijkstra求最短路（堆优化）

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围
1≤n,m≤1.5×10⁵,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 10⁹。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

朴素Dijkstra 时间复杂度为 O(n²)
适合计算稠密图的单源最短路，边数 m² ~ n (边数的平方与点数是同一数量级)

int dijkstra()
{
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    
    //找到从起点到n个点的最短路，需要遍历n次.
    for(int i=0;i 
堆优化Dijkstra 时间复杂度为 O(m*logn)
 适合计算稀疏图的单源最短路，边数m~n (边数与点数是同一数量级且点数比较多，105)
 
#include
using namespace std;
const int N = 1000010;
typedef pair PII;
int n,m;
int h[N],e[N],w[N],ne[N],idx; //稀疏图使用邻接矩阵存储。
int d[N],st[N];
void add(int x,int y,int z)
{
	//w存储着点x到点y的权值。
    e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
}
int dijkstra()
{
    memset(d,0x3f,sizeof d);
    d[1]=0;
    priority_queue,greater > heap; //使用小根堆(优先队列)维护最短边。
    heap.push({0,1}); //堆维护着起点到其余点的距离，从小到大排序 {距离,点}

	//循环使用距起点最近的点更新剩余点的距离。更新后的点和距离都入堆。
    while(heap.size())
    {
        PII t=heap.top();
        heap.pop();
        int ver=t.second,dis=t.first; //距离起点最近的点和距离。

        if(st[ver]) continue; //如果t点最小值已经找到,跳过,避免重复边的重复更新。
        st[ver]=1; //标记t点，t点的最近距离已经找到。

		
        for(int i=h[ver];i!=-1;i=ne[i]) 
        {
            int j=e[i];
            if(d[j]>dis+w[i])
            {
                d[j]=dis+w[i];
                heap.push({d[j],j});
            }
        }

    }
    if(d[n]==0x3f3f3f3f) return -1;
    return d[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    cout<