昂貴的聘禮 POJ - 1062

題目：

傳送門

Input

輸入第一行是兩個整數M，N（1 <= N <= 100），依次表示地位等級差距限制和物品的總數。接下來按照編号從小到大依次給出了N個物品的描述。每個物品的描述開頭是三個非負整數P、L、X（X < N），依次表示該物品的價格、主人的地位等級和替代品總數。接下來X行每行包括兩個整數T和V，分别表示替代品的編号和"優惠價格"。

Output

輸出最少需要的金币數。

Sample Input

1 4

10000 3 2

2 8000

3 5000

1000 2 1

4 200

3000 2 1

4 200

50 2 0

Sample Output

5250

解題思路

1. 建立一個超級原點，找出從這個遠點開始買其他東西所需的價值。

   從這個遠點到其他物品建立邊，權值便為所需要的錢

2. 如果某個物品擁有替代品，代表從替代品建立一條邊到這個物品，這條邊的權值為替代的價值。 代表如果我有了這個替代品，那麼還需要花費多少就能買到這個物品。
3. 因為還有等級制度的限制，是以要枚舉所有等級制度範圍内的所有方案，這時候要注意，因為我們要找的是買第一種物品所需要的錢，是以等級制度中永遠要包含第一種物品

#include<iostream>
#include<cmath>
using namespace std;

const int inf=1e9;
int mpp[101][101];
int dis[101];
int book[101];
int p,ll[101],x;
int m,n; 
int dij(int l,int r)
{
	for(int i=0; i<=n; i++) dis[i]=inf,book[i]=0;
	int u=0;
	book[0]=1;
	dis[0]=0;
	for(int i=0; i<n; i++)
	{
		int min1=1e9;
		for(int j=0; j<=n; j++)
		{
			if(!book[j]&&dis[j]<min1)
			{
				min1=dis[j];
				u=j;
			}
		}
		book[u]=1;
		for(int j=0; j<=n; j++)
		{
			if(!book[j]&&ll[j]>=l&&ll[j]<=r)
			{
				dis[j]=min(dis[j],dis[u]+mpp[u][j]);
			}	
		}
	}
	return dis[1];
}
int main()
{

	cin>>m>>n;
	for(int i=0; i<=n; i++)
		for(int j=0; j<=n; j++)
		{
			if(i==j) mpp[i][j]=0;
			else
			mpp[i][j]=inf;
		}
	for(int i=1; i<=n; i++)
	{
		
		cin>>p>>ll[i]>>x;
		mpp[0][i]=min(mpp[0][i],p);
		while(x--)
		{
			int t,v;
			cin>>t>>v;
			mpp[t][i]=min(mpp[t][i],v);
		}
	}
//	for(int i=0; i<=n; i++)
//	{
//		for(int j=0; j<=n; j++) 
//			cout<<mpp[i][j]<<" ";
//		cout<<endl;
//	}
	int res=1e9;
	for(int i=ll[1]-m; i<=ll[1]; i++)
		res=min(res,dij(i,i+m));
	cout<<res<<endl;
}