AcWing 903. 昂贵的聘礼
原题链接
中等
作者:
零分下一个
,
2023-10-29 17:52:38
,
所有人可见
,
阅读 47
/*
考虑建图方式,
引入一个新的点0,表示冒险家,目标点为1
边权为购买指向人员物品的价格,
考虑等级制度的做法是,
首先酋长的等级,一定要被包含进去,
然后依次枚举range的左端点,每次只更新在range范围内的点
最后取所有最短路的最短路,就是花费的最小金币数量
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int w[N][N],level[N];
int dist[N];
bool st[N];
int m,n,x,cnt,price;
int dijkstra(int l,int r)
{
//由于dijkstra是在循环内部,故必要的初始化是不可省略的
memset(dist,0x3f,sizeof dist);
memset(st,0,sizeof st);
dist[0]=0;
for(int i=0;i<=n;i++)
{
int t=-1;
for(int j=0;j<=n;j++)//寻找第一条最短边,要把0点也包含进去
{
if((!st[j])&&(t==-1||dist[j]<dist[t]))
{
t=j;
}
}
st[t]=true;//用完后,记得标记一下,用于判重
for(int i=0;i<=n;i++)
{
if(level[i]>=l&&level[i]<=r)
dist[i]=min(dist[i],dist[t]+w[t][i]);
}
}
return dist[1];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
//求最短路,先初始化所有边权
memset(w,0x3f,sizeof w);
for(int i=0;i<=n;i++) w[i][i]=0;
for(int i=1;i<=n;i++)
{
cin>>price>>level[i]>>cnt;
w[0][i]=min(w[0][i],price);
while(cnt--)
{
cin>>x>>price;
w[x][i]=(w[x][i],price);
}
}
int res=0x3f3f3f3f;
for(int range=level[1]-m;range<=level[1];range++)
{
res=min(res,dijkstra(range,range+m));
}
cout<<res<<endl;
return 0;
}