一本大道久久a久久精品综合,久久99精品久久久久久秒播,日韩欧美亚洲综合久久

pku 3635

2009年8月1日

題目鏈接：PKU 3635 Full Tank ?

題目分類：一道有趣的bfs（有點難度）

題目分析與算法原型

         題目大意是，給你n個城市（n最大可以到1000）以及每個城市對應(yīng)的油價，這些城市間有m條路徑及每條路徑對應(yīng)的所連接的兩個城市以及路徑的長度（每條路徑連接兩個城市）也告訴了你，給你一輛車，車的油箱儲備量也已知，最后給你剛才n個城市中的某兩個a和b，問你用給你的汽車從a能不能到達b，若能，怎么走才能使得你所花費的油錢最小(路徑每走一單位需要用1升油)，并輸出這個最小的花費..........
        老實說，從看到這道題目開始的將近一整天時間里面我都沒有什么好的思路，知道是一道廣搜，但是還不是特別清楚買油的方式，最后參考了某位大牛前輩的思路，才有了一點眉目（哎，搜索太爛了，有待提高啊）。大致做法是定義一個數(shù)組dis[][],其中dis[i][j]代表汽車到達i號城市，且油箱里面還有j升油的時候的最小花費，創(chuàng)建一個最小堆維護（不用堆優(yōu)化鐵定超時，剛開始堆優(yōu)化沒寫好，貢獻了2次TLE），從隊列中取出最小花費的那個，然后以它作為節(jié)點擴展開來（注意，這道題目城市數(shù)比較大，采用鄰接表存儲比較好）..........

        具體做法如下：
1.每次從隊列中彈出第一個元素，因為采用了最小堆維護，這樣可以確保彈出的元素一定是隊列中花費最小那個元素

2. 假設(shè)彈出的元素對應(yīng)的是dij[C][L]（既是在C號城市，剩下L升汽油時的最小花費）然后我們每次只買一升油，此時所花費的錢算上剛才一共是dij[C][L]+price[C](price[C]代表C號城市的油價)，然后更新，取dij[C][L+1]=Min(dij[C][L+1],dij[C][L]+price[C]),新擴展的元素入隊列

3.枚舉每個和C號城市相互鄰接的城市X,如果當(dāng)前儲備的油L>=d(d為C到X的路徑長度)，說明可以開到X城市，此時油剩下L-d,然后更新，取dis[X][L-d]=Min(dis[X][L-d],dis[C][L]),相應(yīng)的元素入隊列.

Code:

1

#include<stdio.h>
2

#define INF 1000000000
3

#define len 1005
4

int map[len][len],price[len],cost[len][len],n,m,count;
5

int dis[len][105],flag[len][105];
6

struct node
7

{
8

int city,fuel,money;
9

}queue[1000000];
10

void down_min_heap(int n,int h)//n表示堆元素的個數(shù)，從0開始編號,從h開始往下調(diào)整
11

{
12

int i=h,j=2*i+1;
13

node temp=queue[i];
14

while(j<n)
15

{
16

if(j<n-1&&queue[j].money>queue[j+1].money)j++;//若右孩子存在，且右孩子比較小，取右
17

if(temp.money<queue[j].money)break;
18

else
19

{
20

queue[i]=queue[j];
21

i=j;
22

j=2*i+1;
23

}
24

}
25

queue[i]=temp;
26

}
27

void up_min_heap(int s)
28

{
29

while (s>0&&queue[s].money<queue[(s-1)/2].money) //從s開始往上調(diào)整
30

{
31

node tt=queue[s];
32

queue[s]=queue[(s-1)/2];
33

queue[(s-1)/2]=tt;
34

s = (s-1)/2;
35

}
36

}
37

node pop()
38

{
39

node res=queue[0];
40

queue[0]=queue[count-1];
41

count--;
42

down_min_heap(count,0);
43

return res;
44

}
45

void push(int c,int f,int m)
46

{
47

queue[count].city=c;
48

queue[count].fuel=f;
49

queue[count].money=m;
50

count++;
51

up_min_heap(count-1);
52

}
53

int bfs(int cap,int start,int end)
54

{
55

int i,j;
56

count =0;
57

for(i=0;i<n;i++)
58

for(j=0;j<=cap;j++)
59

dis[i][j]=INF,flag[i][j]=0;
60

push(start,0,0);
62

dis[start][0] = 0;
63

while (count>0)
65

{
66

node u=pop();
67

int city=u.city,left=u.fuel;
68

if (flag[city][left]) continue;
69

if (city==end) break;
70

if (left<cap && dis[city][left+1]>dis[city][left]+price[city])
71

{
72

dis[city][left+1]=dis[city][left]+price[city];
73

push(city, left+1, dis[city][left+1]);
74

}
75

for (i=1; i<= map[city][0];i++)
76

{
77

int v=map[city][i], nc=cost[city][i];
78

if (left>=nc && dis[v][left-nc]>dis[city][left])
79

{
80

dis[v][left-nc]=dis[city][left];
81

push(v,left-nc,dis[v][left-nc]);
82

}
83

}
84

flag[city][left] = 1;
85

}
86

return dis[end][0];
87

}
88

int main()
89

{
90

int i,q;
91

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

{
93

for(i=0;i<n;i++)
94

{
95

scanf("%d",&price[i]);
96

map[i][0]=0;
97

}
98

for(i=0;i<m;i++) //采用鄰接表的方式存
99

{
100

int a,b,l;
101

scanf("%d%d%d",&a,&b,&l);
102

map[a][++map[a][0]]=b;
103

cost[a][map[a][0]]=l;
104

map[b][++map[b][0]]=a;
105

cost[b][map[b][0]]=l;
106

}
107

scanf("%d",&q);
108

for(i=0;i<q;i++)
109

{
110

int cap,start,end;
111

scanf("%d%d%d",&cap,&start,&end);
112

int res=bfs(cap,start,end);
113

if(res<INF)printf("%d\n",res);
114

else printf("impossible\n");
115

}
116

}
117

return 1;
118

}
119

posted on 2009-08-01 16:02 蝸牛也Coding 閱讀(1573) 評論(2) 編輯收藏引用

# re: pku 3635 2009-08-01 16:12 Vincent

# re: pku 3635 2009-08-04 17:25 付翔

pku 3635

評論

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

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



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