迪杰特斯拉算法+堆优化

/*
O(eloge)堆优化dj算法，在n的数量级>=1e5时必须采用这种堆优化+邻接表方式
*/

struct node{
    int p, w;
    node(int a, int b):p(a), w(b){}
    bool operator< (const node& b) const
    {
        return w > b.w;
    }
};
vector<node> g[N];
priority_queue<node> sup;
void dijkstra(int start)
{
    memset(dis, 0x3f, sizeof(dis));
    dis[start] = 0; pre[start] = start;
    sup.push(node(start, 0));
    while (!sup.empty())
    {
        node front = sup.top();
        sup.pop();  int tempv = front.p;
        if (visit[tempv]) continue;
        visit[tempv] = true;
        for (int i = 0; i < g[tempv].size(); i++)
        {
            int p = g[tempv][i].p;
            if (!visit[p] && dis[tempv]+g[tempv][i].w < dis[p])
            {
                dis[p] = dis[tempv]+g[tempv][i].w;
                pre[p] = tempv;
                sup.push(node(p, dis[p]));
            }
        }
    }
}