Djikstar堆优化版本 纯代码

#include <bits/stdc++.h>

#define x first
#define y second
#define PII pair<int,int>

using namespace std;

const int N = 1e4+5 ,M = 110 ,INF = 0x3f3f3f3f;

int e[N],w[N],ne[N],h[M],idx;
int dist[M],lev[M];
bool st[M];

int n,m;

priority_queue<PII,vector<PII>,greater<PII> > q;

void add(int a ,int b ,int c)
{
    e[idx] = b ,w[idx] = c, ne[idx] = h[a] , h[a] = idx ++;
}

int Djikstar(int down ,int up)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[0] = 0;
    q.push({0,0});

    while(q.size())
    {
        PII t = q.top() ; q.pop();

        if(st[t.y]) continue;
        st[t.y] = true;

        for(int i = h[t.y] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(lev[j] >= down && lev[j] <= up && (dist[j] > t.x + w[i]))
            {
                dist[j] = t.x + w[i];
                q.push({dist[j],j});
            }
        }
    }

    return dist[1];
}

int main()
{
    memset(h,-1,sizeof h);
    cin >> m >> n;

    for(int i = 1 ;i <= n ; i ++)
    {
        int prices , cnt;
        cin >> prices >> lev[i] >> cnt;
        add(0, i , prices);
        while(cnt --)
        {
            int id , cost; cin >> id >> cost;
            add(id , i , cost);
        }
    }

    int res = INF;

    for(int i = lev[1] - m ; i <= lev[1]; i ++) res = min(res , Djikstar(i , i + m));

    cout << res << endl;
    return 0;
}