POJ-1062

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：”嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。”探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。

为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的”优惠”Vi。如果两人地位等级差距超过了M，就不能”间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

输入第一行是两个整数M，N（1 <= N <= 100），依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X < N），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和”优惠价格”。

输出最少需要的金币数。

输入示例：

1
2
3
4
5
6
7
8
9
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0

输出示例：

1
5250

题目大意：

一开始需要n金币，每个物品都有自己的价值，你可以用其他物品来抵消一部分金币（优惠价格），而用来抵消的物品也可以由其他物品来抵消该物品的一部分，如此往复。并且主人是分等级的，要确保交换物品过程中任何两个人的等级差距都不能超过M。
问最少需要的金币数量。

思路：

把每个物品看成结点，B物品可以抵消A物品的一部分,表示A有一条边指向B,边权是替代品的优惠价格，点权为该物品的价值。

可以求第一个物品到其他物品的最短路，松弛操作为：

1
dis[v] > dis[u] + u到v的边权

这样求得的dis为每个顶点到起点的优惠价格，而到当前点的总花费为：

1
dis[i] + coin[i] //优惠价格+当前物品的价格

而题目还有一层约束条件为物品交换不能超过等级差距。
我们就需要检查每个点到起点的等级差了。
例如起点的等级为5，等级差距为3，则要枚举的区间为 3 ~ 5、4 ~ 6、5 ~ 7 ，在每个区间中，求符合等级差距的点，并求起点到该点的最短路（这里比较绕，建议多思考下）。最后答案取一个最小值即可。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;
struct Edge{
    int to,cost;
    Edge(){};
    Edge(int _to,int _cost){
        to = _to;
        cost = _cost;
    };
};

struct qnode{
    int v,cost;
    qnode(int _v, int _cost){
        v = _v;
        cost = _cost;
    }
    qnode(){}
    bool operator <(const qnode &b)const{
        return cost > b.cost;
    }
};
vector<Edge> G[MAXN];

int coin[MAXN]; //价值多少金币 
int dis[MAXN];	//最少优惠 
int vis[MAXN];	
int pos[MAXN];  //等级 
int M,N;
int ans;
 void Dijkstra(int S,int N){
 	for(int i = 1; i <= N; i++){
 		dis[i] = S== i ? 0 : INF;
	 }
     priority_queue<qnode> pq;
     pq.push(qnode(S,dis[S]));
     qnode temp;
     while(pq.size()){
         temp = pq.top();pq.pop();
         int u = temp.v;
         if(vis[u])continue;
         vis[u] = 1;
         for(int i = 0; i < G[u].size(); i++){
             int v = G[u][i].to;
             int vc = G[u][i].cost;
             if(!vis[v] && dis[v] > dis[u] + vc){
                dis[v] = dis[u] + vc;	
                //更新答案 
                ans = min(ans,dis[v] + coin[v]);
                pq.push(qnode(v,dis[v]));
             }
         }
     }
//     for(int i = 1; i <= N; i++){
//     	ans = min(ans,dis[i] + coin[i]);		
//	 } 
 }

void init(int N){
	for(int i = 0; i <= N; i++){
		G[i].clear();
	}
} 

int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d %d",&M,&N);
    init(N);
    for(int i = 1; i <= N; i++){
        int c,r,n;
        scanf("%d%d%d",&c,&r,&n);
        coin[i] = c;
        pos[i] = r;

        for(int j = 1; j <= n; j++){
            int t,cost;
            scanf("%d%d",&t,&cost);
            G[i].push_back(Edge(t,cost));
        }
    }
    //设最大值为起始值 
    ans = coin[1];
    for(int i = 0; i <= M; i++){
    	//更新每个点是否在当前区间内 
    	for(int j = 1; j <= N; j++){
    		if(pos[j] >= pos[1]-M+i && pos[j] <= pos[1]+i) vis[j] = 0;
    		else vis[j] = 1;
		}
		//求一下当前区间的最短路。 
		Dijkstra(1,N);
	}
    printf("%d",ans);
    return 0;
}