DJ（）

T——P大神 · 2019-11-14 11:19:21 · 个人记录

// Dj()堆优化。

priority_queue<pair<ll,ll> >q;
    for (ll i = 1;i <= n;i++)
    dis[i] = inf;
    dis[1] = 1;
    q.push(make_pair(0,1));
//  vis[1] = true;
    while (!q.empty())
    {
        ll di = q.top().second;
        q.pop();
        if (vis[di])
        continue;
        vis[di] = true;
        for (ll i = head[di];i;i = e[i].next)
        {
            ll v = e[i].to;
            ll w = e[i].val;
            if(dis[v] > dis[di] + w) 
            {
                dis[v] = dis[di] + w;
                q.push(make_pair(-dis[v],v));
            }
            //  cout << dis[v] << endl;
        }
    }
    cout << dis[n] << endl;

参考例题： P2384,P4779.