九九精品99久久久香蕉,久久精品亚洲福利,久久国产精品无码网站

pku 1062

2009年7月24日

題目鏈接：PKU 1062 昂貴的聘禮

分類：最短路

題目分析與算法原型
這道題目其實(shí)就是一個(gè)最短路徑，不過是增加了等級(jí)限制，可以這樣考慮，增加一個(gè)節(jié)點(diǎn)n+1對(duì)應(yīng)第n+1件物品，對(duì)于前面1到n每一個(gè)物品，增加一條其到第n+1個(gè)物品的邊，該邊的權(quán)值為該物品的原來價(jià)格，對(duì)于題目給定的輸入數(shù)據(jù)，若物品x,能用物品y換的一個(gè)優(yōu)惠價(jià)格p,則增加一條從x到y(tǒng)的邊，其權(quán)值為p,這樣一來，就構(gòu)好圖了，問題就轉(zhuǎn)換成了求從節(jié)點(diǎn)1到節(jié)點(diǎn)n+1的最短路徑問題了，當(dāng)然了，該題目還有一個(gè)等級(jí)限制，所以在運(yùn)用Dijkastra的時(shí)候，應(yīng)該注意當(dāng)前的路徑中最大等級(jí)和最小等級(jí)間的差是否超過了給定的m，若超過了，則當(dāng)前的路徑就不行了，具體處理方法可以設(shè)置兩個(gè)變量_min,_max分別存的是路徑中最小和最大的等級(jí)，然后每當(dāng)要加入節(jié)點(diǎn)時(shí)判斷是否滿足，對(duì)于不滿足的點(diǎn)，標(biāo)記位仍然置為1，但是下面的操作就Continue略過就行了。

Code:

1

#include<stdio.h>
2

#include<string.h>
3

#define max 0x7fffffff
4

#define len 110
5

int m,n,p,l,x,map[len][len],i,j,t,v,dis[len],flag[len],dj[len],min,u;
7

int _min,_max;
8

void init()
10

{
11

for(i=1;i<=n;i++)
12

for(j=1;j<=n;j++)
13

{
14

if(i==j)map[i][j]=0;
15

else map[i][j]=max;
16

}
17

}
18

void dij()
20

{
21

int xiao,da,go;
22

for(i=1;i<=n+1;i++)dis[i]=map[1][i];
23

flag[1]=1;
24

for(i=1;i<=n;i++)
26

{
27

min=max;
28

go=0;
29

for(j=1;j<=n+1;j++)
30

if(flag[j]==0&&dis[j]<min)
31

{
32

u=j;
33

min=dis[j];
34

}
35

flag[u]=1;
36

if(dj[u]<_min)
37

{
38

xiao=_min;
39

_min=dj[u];
40

if(_max-_min>m)
41

{
42

go=1;
43

_min=xiao;
44

}
45

}
46

else if(dj[u]>_max)
47

{
48

da=_max;
49

_max=dj[u];
50

if(_max-_min>m)
51

{
52

go=1;
53

_max=da;
54

}
55

}
56

if(go)continue;
57

for(j=1;j<=n+1;j++)
58

if(flag[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
59

dis[j]=dis[u]+map[u][j];
60

}
61

}
63

int main()
65

{
66

while(scanf("%d%d",&m,&n)!=EOF)
67

{
68

init();
69

memset(flag,0,sizeof(flag));
70

for(i=1;i<=n;i++)
71

{
72

scanf("%d%d%d",&p,&l,&x);
73

map[i][n+1]=p;
74

dj[i]=l;
75

for(j=1;j<=x;j++)
76

{
77

scanf("%d%d",&t,&v);
78

map[i][t]=v;
79

}
80

}
81

_max=dj[1];
82

_min=dj[1];
83

dij();
84

printf("%d\n",dis[n+1]);
85

}
86

return 0;
87

}
88

posted on 2009-07-24 19:30 蝸牛也Coding 閱讀(761) 評(píng)論(4) 編輯收藏引用

評(píng)論

# re: pku 1062 2009-09-12 16:36 姓李

在下有疑問，如果有一個(gè)點(diǎn)，第一次被選擇之后，發(fā)現(xiàn)其不符等級(jí)限制，那么就不更新了，可是有沒有可能最小的價(jià)錢是要經(jīng)過這個(gè)點(diǎn)呢？
例如下面的數(shù)據(jù)
1 5
10000 3 2
2 8000
3 8000
3000 4 1
4 400
3000 2 1
4 500
1000 3 1
5 100
100 2 0

難道結(jié)果不是5700嗎？
不懂啊，如果有空幫忙解釋一下，我的郵箱lijh_402@yeah.net 回復(fù) 更多評(píng)論

# re: pku 1062 2009-10-01 22:44 JustCodeIT

我也不太懂樓主的算法原理，為什么你不用枚舉呢？
同樓上的疑問？回復(fù) 更多評(píng)論

# re: pku 1062 2010-07-20 14:52 walker01

增加一個(gè)節(jié)點(diǎn)n+1, 妙！回復(fù) 更多評(píng)論

# re: pku 1062 2011-06-23 11:09 Firefrog

樓主的代碼雖然可以AC，但是是錯(cuò)的。
你試一下這個(gè)數(shù)據(jù)：
1 4
10000 3 2
2 1
3 3
1000 2 2
4 1
3 1
1000 3 1
4 2
100 4 0
正確答案應(yīng)該是：
105
樓主的代碼輸出的是 1001。回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: pku 1062 2009-09-12 16:36 姓李

# re: pku 1062 2009-10-01 22:44 JustCodeIT

# re: pku 1062 2010-07-20 14:52 walker01

# re: pku 1062 2011-06-23 11:09 Firefrog

pku 1062

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜