欧美成人按摩,久久亚洲国产精品一区二区 ,牛牛国产精品

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

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

6

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

9

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

19

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

25

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

62

}
63

64

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

89

posted on 2009-07-24 19:30 蝸牛也Coding 閱讀(777) 評論(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 回復更多評論