原题链接

昂贵的聘礼.png

前置知识

Dijkstra
链式前向星
虚拟源点

分析

本题的难点在于如何建图将原问题抽象成一个最短路问题以及如何处理等级限制。
以下为样例建图示意
样例.png
最后只需要枚举允许的等级区间，在每一个区间以超级源点为起点跑一遍Dijkstra取所有答案的min，便是最终答案。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N = 105,M = N * N,INF = 0x3f3f3f3f;
int h[N],ne[M],e[M],w[M],idx = 1;
int m,n,level[N],dis[N];
bool st[N];

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

int djk(int l,int r)
{
    memset(dis,0x3f,sizeof dis);
    memset(st,0,sizeof st);
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    
    dis[0] = 0;
    heap.push({0,0});
    
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i=h[ver];i!=-1;i = ne[i])
        {
            int num = e[i];
            if(dis[num] > dis[ver] + w[i] && level[num] >= l && level[num] <= r)
            {
                dis[num] = dis[ver] + w[i];
                heap.push({dis[num],num});
            }
        }
    }
    return dis[1];
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int p,l,x;
        cin>>p>>l>>x;
        level[i] = l;
        add(0,i,p); //超级源点
        while(x--)
        {
            int num,cost;
            cin>>num>>cost;
            add(num,i,cost);
        }
    }
    
    int res = INF;
    for(int i=level[1]-m;i<=level[1];i++) res = min(res,djk(i,i+m));
    cout<<res<<endl;
    return 0;
}