热久久视久久精品18,办公室久久精品,麻豆久久

pku 1062

2009年7月24日

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

分類：最短路

題目分析與算法原型
這道題目其實就是一個最短路徑，不過是增加了等級限制，可以這樣考慮，增加一個節點n+1對應第n+1件物品，對于前面1到n每一個物品，增加一條其到第n+1個物品的邊，該邊的權值為該物品的原來價格，對于題目給定的輸入數據，若物品x,能用物品y換的一個優惠價格p,則增加一條從x到y的邊，其權值為p,這樣一來，就構好圖了，問題就轉換成了求從節點1到節點n+1的最短路徑問題了，當然了，該題目還有一個等級限制，所以在運用Dijkastra的時候，應該注意當前的路徑中最大等級和最小等級間的差是否超過了給定的m，若超過了，則當前的路徑就不行了，具體處理方法可以設置兩個變量_min,_max分別存的是路徑中最小和最大的等級，然后每當要加入節點時判斷是否滿足，對于不滿足的點，標記位仍然置為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) 評論(4) 編輯收藏引用

在下有疑問，如果有一個點，第一次被選擇之后，發現其不符等級限制，那么就不更新了，可是有沒有可能最小的價錢是要經過這個點呢？
例如下面的數據
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

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

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

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

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

增加一個節點n+1, 妙！回復更多評論

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

樓主的代碼雖然可以AC，但是是錯的。
你試一下這個數據：
1 4
10000 3 2
2 1
3 3
1000 2 2
4 1
3 1
1000 3 1
4 2
100 4 0
正確答案應該是：
105
樓主的代碼輸出的是 1001。回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 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

評論

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜