转载请注明出处：優 YoU http://user.qzone.qq.com/289065406/blog/1299338542
提示：难得的中文题。。虽然语言相通但是不好解决。。。都说便宜没好货，这是真的= =
最短路问题，dijkstra算法的运用。。。很多同学对dijkstra有一种与生俱来的恐惧，首当其冲就是它的名字。。说实在我现在也不知道怎么念它O(∩_∩)O哈哈~其实dijkstra很简单的，最难也就它的名字，不懂得同学去翻书，这里我不解释dijkstra，我只说一个我认为能够很好理解dijkstra精髓的关键点：
新源点合并到旧源点时，新源点到旧源点的边权的移交（也可理解为松弛）
弄清了这个，dijkstra就不难了，我觉得dijkstra和Prim有异曲同工之妙
每个物品看成一个节点，
酋长的允诺也看作一个物品，
如果一个物品加上金币可以交换另一个物品，
则这两个节点之间有边，权值为金币数，求第一个节点到所有节点的最短路。
因为有等级限制，所以枚举每个点作为最低等级，选取符合所有符合等级
限制
的点
最短路问题，不过因为存在着等级的差异所以需要枚举一下。本题的思路就是对冒险者的等级进行枚举，也就是说冒险者只能和在他等级以上的人进行交易。这样枚举的好处是能够把所有的情况都考虑进去。有一点需要注意：酋长的等级不一定是最高的
构图时要注意的是，酉长的承诺不是
最初的源点，它是一个目标点，也就是说点到点的指向方向是由
无替代品的点
逐渐指向到
酉长的承诺
1
点，题意说明的是一个回溯的过程，因此可以定义一个最初的源点
0
点，它到其他各点的权值就是每个物品的原价，而点
A
到点
B
的权值
就是
物品
B
在有第
A
号替代品情况下的优惠价
1
//
Memory Time
2
//
300K 32MS
3
4
#include
<
iostream
>
5
using
namespace
std;
6
7
const
int
inf
=
0x7fffffff
;
//
无限大
8
9
int
M,N;
//
M为等级差，N为物品数目
10
int
price[
101
][
101
];
//
物品i在有第t号替代品情况下的优惠价pricr[t][i],当t=0时说明i无替代品，此时为原价
11
int
lv[
101
];
//
第i号物品主人的等级lv[i]
12
int
x[
101
];
//
第i号物品的替代品总数x[i]
13
14
int
dist[
101
];
//
最初的源点0到任意点i的最初距离（权值），相当于每个物品的原价
15
16
bool
vist[
101
];
//
记录点i是否已被访问
17
18
/*
Initial and Input
*/
19
20
void
data_init()
21
{
22
memset(price,
0
,
sizeof
(price));
23
memset(lv,
0
,
sizeof
(lv));
24
memset(dist,inf,
sizeof
(dist));
25
memset(vist,
false
,
sizeof
(vist));
26
27
cin
>>
M
>>
N;
28
for
(
int
i
=
1
;i
<=
N;i
++
)
29
{
30
cin
>>
price[
0
][i]
>>
lv[i]
>>
x[i];
//
price[0][i]物品i无替代品时的原价
31
32
for
(
int
j
=
1
;j
<=
x[i];j
++
)
33
{
34
int
t,u;
//
t替代品编号，u优惠价(临时变量)
35
cin
>>
t
>>
u;
36
price[t][i]
=
u;
//
物品i在有第t号替代品情况下的优惠价，即点t到点i的权值
37
}
38
}
39
}
40
41
/*
Dijkstra Algorithm
*/
42
43
int
dijkstra()
44
{
45
46
int
node;
//
记录与当前源点距离最短的点
47
int
sd;
//
最短距离
48
int
i,j;
49
50
for
(i
=
1
;i
<=
N;i
++
)
51
dist[i]
=
price[
0
][i];
//
假设最初的源点就是0点，初始化最初源点到各点的权值dist[i]
52
53
for
(i
=
1
;i
<=
N;i
++
)
//
由于1点是目标点，因此最坏的打算是进行n次寻找源点到其他点的最短路，并合并这两点（不再访问相当于合并了）
54
{
55
node
=
0
;
56
sd
=
inf;
57
for
(j
=
1
;j
<=
N;j
++
)
58
{
59
if
(
!
vist[j]
&&
sd
>
dist[j])
//
在未访问的点中，寻找最短的一条
60
{
61
sd
=
dist[j];
62
node
=
j;
//
记录该点
63
}
64
}
65
if
(node
==
0
)
//
若node没有变化，说明所有点都被访问，最短路寻找完毕
66
break
;
67
68
vist[node]
=
true
;
//
记录node点已被访问
69
for
(j
=
1
;j
<=
N;j
++
)
70
{
71
if
(
!
vist[j]
&&
price[node][j]
>
0
&&
dist[j]
>
dist[node]
+
price[node][j])
//
把未访问但与node（新源点）连通的点进行松弛
72
dist[j]
=
dist[node]
+
price[node][j];
73
}
74
}
75
return
dist[
1
];
//
返回当前次交易后目标点1在等级lv[i]约束下的最短距离
76
}
77
78
int
main()
79
{
80
data_init();
//
初始化并输入数据
81
82
int
temp_price;
//
当前次交易后目标点1在等级lv[i]约束下的最少价格
83
int
maxlv;
//
最大等级(酉长的等级不一定是最大的)
84
int
minprice
=
inf;
//
最低价格(初始化为无限大)
85
86
for
(
int
i
=
1
;i
<=
N;i
++
)
87
{
88
/*
在等级限制下，寻找允许被当前点访问的点
*/
89
90
maxlv
=
lv[i];
//
把当前物品的等级暂时看做最高等级
91
for
(
int
j
=
1
;j
<=
N;j
++
)
//
遍历其他各点
92
{
93
if
(lv[j]
>
maxlv
||
maxlv
-
lv[j]
>
M)
//
当其它物品j的等级比当前物品高(保证单向性)，或者两者等级之差超出限制M时
94
vist[j]
=
true
;
//
物品j则强制定义为“已访问”状态，不参与后续操作
95
else
96
vist[j]
=
false
;
//
否则物品j定义为“未访问”状态，参与后续操作
97
}
98
99
temp_price
=
dijkstra();
//
记录当前次交易后目标点1在等级lv[i]约束下的最短距离(最少价格)
100
101
if
(minprice
>
temp_price)
//
寻找各次交易后的最少价格，最终确认最少价格
102
minprice
=
temp_price;
103
}
104
cout
<<
minprice
<<
endl;
105
106
return
0
;
107
}
