图论——最短路——堆优化dijstra

1   流程

    dist[所有点] = +∞
    dist[起始点] = 0

    小根堆
    存入起始点(倒存方便排序)

    while(堆不空)
    {
        取没走过的堆顶编号t
        st[t] == true
        用t更新其他所有出点(入堆)
    }

    判断是否能走

2   code

    int dijstra( int u )
    {
        memset( dist, INF, sizeof dist );
        dist[u] = 0;

        priority_queue< PII, vector<PII>, greater<PII> > heap;
        heap.push( { 0, u } );

        while( heap.size() )
        {
            int t = heap.top().second;
            heap.pop();
            if( st[t] )
                continue;

            st[t] = true;

            for( int i = h[t]; i; i = ne[i])
            {
                int y = e[i], z = w[i];
                if( dist[y] > dist[t] + z )
                {
                    dist[y] = dist[t] + z;
                    heap.push( { dist[y], y } );
                }

            }
        }

        if( dist[n] == 0x3f3f3f3f )
            return -1;
        else
            return dist[n];
    }