轉載請注明出處：優 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
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
