每日一题----昂贵的婚礼

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
//本题酋长的允诺也算一个物品,最后一定要交给酋长，那么等级不能超过酋长的等级范围const int N = 150 * 150,M = N;
typedef pair<int,int> pll;
int dist[N];//距离数组,这里代表到当前点的花费
int n,m;
int level[N];
//每次交易只能在等级限制范围内可以交易
bool st[N];
int e[M],h[N],idx,ne[M],w[M];
int price[N];//每个物品的价值,下标就是编号
void add(int a,int b,int c)
{e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int dijkstra(int l,int r)
{memset(dist,0x3f,sizeof dist);memset(st,0,sizeof st);dist[0] = 0;priority_queue<pll,vector<pll>,greater<pll>> heap;heap.push({0,0});//第一个是点，第二个是当前点的距离//dijkstra堆优化算法,优化在取路径最短那里while(heap.size()){auto t = heap.top().second;heap.pop();if(st[t]) continue;st[t] = true;for(int i = h[t];i != -1;i = ne[i]){int j = e[i];if(dist[j] > dist[t] + w[i] && level[j] >= l && level[j] <= r){dist[j] = dist[t] +  w[i];heap.push({dist[j],j});}}}return dist[1];
}
int main()
{cin>>m>>n;//0是虚拟源点，比如到3要10000，不用其他物品换，直接买得到的价格//比如拿2去换1的物品，就用箭头指向1memset(h,-1,sizeof h);for(int i = 1;i <= n;i++){int cnt;cin>>price[i]>>level[i]>>cnt;add(0,i,price[i]);for(int j = 0;j < cnt;j++){int id,cost;cin>>id>>cost;add(id,i,cost);//id指向i代表id换i所需的花费}}int res = 0x3f3f3f3f;//枚举酋长允诺的等级区间之内for(int i = level[1] - m;i <= level[1];i++){res = min(res,dijkstra(i,i + m));}cout<<res<<endl;return 0;
}