堆优化 Dijkstra算法

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

#define N 1000001
#define INF 2000000000

int n,m,head[N],cnt,dis[N];

bool vis[N];

struct edge
{
    int to,value,net; 
}
e[N << 1];

typedef pair <int,int> PII;

priority_queue < pair<int,int>,vector <pair<int,int>>,greater<pair<int,int>> > q;

void add(int from,int to,int value)
{
    e[++cnt] = (edge){to,value,head[from]};
    head[from] = cnt;
}

int main()
{
    scanf ("%d %d",&n,&m);
    for (int i = 1; i <= m; i++)
    {
        int x ,y, z;
        scanf ("%d %d %d",&x,&y,&z);
        add(x,y,z);
    }
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    dis[1] = 0;
    q.push({0,1});
    while (!q.empty())
    {
        int diss = q.top().first;
        int now = q.top().second;
        q.pop();
        if (vis[now])   // 与 spfa 不同之处
            continue;
        vis[now] = 1;
        for (int i = head[now]; i; i = e[i].net)
        {
            int too = e[i].to;
            if (dis[too] > diss + e[i].value)
            {
                dis[too] = diss + e[i].value;
                q.push({dis[too],too});
            }
        }
    }
    if (dis[n] != 2000000000)
        printf ("%d",dis[n]);
    else
        printf ("-1");
    return 0;
}