gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

1.?re: Pku 2774--Long Long Message（后綴樹）
求教大牛，那個Lt屬性是記錄什么的
--dereky
2.?re: POJ 2481(樹狀數組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數組)
@gzwzm06
兩個相同一起比較也就是兩個區間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數組)
評論內容較長,點擊標題查看
--gzwzm06

POJ 1511(Dij + Heap)

1

#include <stdio.h>
2

#include <cstring>
3

4

const int MAXN = 10001001 ;
5

const __int64 INT_MAX = 2000000000 ;
6

7

8

//edge 原圖 redge 反圖
9

//用反圖求Dij，就可算出其他點到源點的最短路徑(非常有用)
10

struct EDGE
11

{
12

int ID ;
13

__int64 wg ;
14

struct EDGE *next ;
15

}edge[MAXN], redge[MAXN], g_Temp[MAXN * 2] ;
16

17

int g_Level = 0 ;
18

19

int V , E ;
20

__int64 weight[MAXN] ;
21

__int64 ecost[MAXN] ;
22

bool visited[MAXN] ;
23

24

struct Heap
25

{
26

int ID ;
27

__int64 wg ;
28

29

void operator = ( const Heap& x )
30

{
31

ID = x.ID ;
32

wg = x.wg ;
33

}
34

35

} HeapArray[MAXN * 2] ;
36

37

int g_Htail ;
38

39

inline void HeapPush( const int& id, const __int64& val )
40

{
41

int currentPos, parentPos ;
42

43

currentPos = g_Htail ;
44

parentPos = (( currentPos - 1 ) >> 1) ;
45

46

HeapArray[g_Htail].ID = id ;
47

HeapArray[g_Htail++].wg = val ;
48

49

while ( currentPos != 0 )
50

{
51

if ( HeapArray[parentPos].wg <= val )
52

break ;
53

else {
54

HeapArray[currentPos] = HeapArray[parentPos] ;
55

currentPos = parentPos ;
56

parentPos = (( currentPos - 1 ) >> 1) ;
57

}
58

}
59

60

HeapArray[currentPos].ID = id ;
61

HeapArray[currentPos].wg = val ;
62

}
63

64

inline int HeapPop()
65

{
66

if ( g_Htail == 0 )
67

return -1 ;
68

69

int currentPos, childPos ;
70

71

int result = HeapArray[0].ID ;
72

73

HeapArray[0] = HeapArray[g_Htail - 1] ;
74

g_Htail-- ;
75

76

currentPos = 0 ;
77

childPos = 1 ;
78

Heap target = HeapArray[0] ;
79

80

while ( childPos < g_Htail )
81

{
82

if ( (childPos + 1 < g_Htail)
83

&& (HeapArray[childPos + 1].wg <= HeapArray[childPos].wg) )
84

{
85

childPos = childPos + 1 ;
86

}
87

88

if ( target.wg <= HeapArray[childPos].wg )
89

break;
90

else {
91

HeapArray[currentPos] = HeapArray[childPos] ;
92

currentPos = childPos ;
93

childPos = 2 * currentPos + 1 ;
94

}
95

}
96

97

HeapArray[currentPos] = target ;
98

99

return result ;
100

}
101

102

void HeapDij( int src, int dis, bool rg = false )
103

{
104

int i ;
105

106

for ( i = 1 ; i <= V ; ++i )
107

{
108

ecost[i] = INT_MAX ;
109

visited[i] = false ;
110

}
111

ecost[src] = 0 ;
112

EDGE *ptr ;
113

114

if ( !rg )
115

ptr = edge[src].next ;
116

else
117

ptr = redge[src].next ;
118

119

while ( ptr ){
120

ecost[ptr->ID] = ptr->wg ;
121

ptr = ptr->next ;
122

}
123

124

g_Htail = 0 ;
125

126

for ( i = 1 ; i <= V ; ++i )
127

{
128

HeapPush( i , ecost[i] ) ;
129

}
130

131

visited[src] = true ;
132

133

for ( i = 1 ; i < V ; ++i )
134

{
135

int v = HeapPop() ;
136

137

while ( visited[v] )
138

v = HeapPop() ;
139

140

if ( ecost[v] == INT_MAX )
141

break ;
142

143

visited[v] = true ;
144

145

if ( !rg )
146

ptr = edge[v].next ;
147

else
148

ptr = redge[v].next ;
149

150

while ( ptr ){
151

152

if ( !visited[ptr->ID] && ecost[ptr->ID] > ecost[v] + ptr->wg )
153

{
154

ecost[ptr->ID] = ecost[v] + ptr->wg ;
155

HeapPush( ptr->ID , ecost[ptr->ID] ) ;
156

}
157

ptr = ptr->next ;
158

}
159

}
160

}
161

162

void Init()
163

{
164

int i ;
165

166

for ( i = 0 ; i <= V ; ++i )
167

{
168

edge[i].next = NULL ;
169

redge[i].next = NULL ;
170

}
171

g_Htail = 0 ;
172

g_Level = 0 ;
173

}
174

175

inline void Insert( const int& x, const int& y, const __int64& val )
176

{
177

EDGE *ptr = &g_Temp[g_Level++] ;
178

ptr->ID = y;
179

ptr->wg = val ;
180

ptr->next = edge[x].next ;
181

edge[x].next = ptr ;
182

183

ptr = &g_Temp[g_Level++] ;
184

ptr->ID = x;
185

ptr->wg = val ;
186

ptr->next = redge[y].next ;
187

redge[y].next = ptr ;
188

}
189

190

int main()
191

{
192

int j , x , y , t ;
193

int w ;
194

195

// freopen("in.txt", "r", stdin) ;
196

197

scanf("%d", &t) ;
198

while ( t-- )
199

{
200

scanf("%d %d", &V, &E) ;
201

Init() ;
202

203

for ( j = 1 ; j <= E ; ++j )
204

{
205

scanf("%d %d %d", &x, &y, &w) ;
206

Insert( x, y, w ) ;
207

}
208

209

__int64 ans = 0 ;
210

211

//先求1到其他點的最短路徑
212

HeapDij( 1, V ) ;
213

214

for ( j = 2 ; j <= V ; ++j )
215

ans += ecost[j] ;
216

217

//在求其他點到1的最短路徑
218

HeapDij( 1, V, true ) ;
219

220

for ( j = 2 ; j <= V ; ++j )
221

ans += ecost[j] ;
222

223

printf("%I64d\n", ans) ;
224

}
225

226

return 0 ;
227

}

posted on 2008-11-19 23:18 巫閱讀(483) 評論(0) 編輯收藏引用所屬分類: 圖論

只有注冊用戶登錄后才能發表評論。


相關文章: POJ 3662--Telephone Lines(二分枚舉 + Dij) POJ 3268(最短路徑 SPFA) POJ 1511(SPFA) POJ 1511(Dij + Heap) POJ 1094(簡單的拓撲排序) Pku 2226--Muddy Fields Pku 3678--Katu Puzzle

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品