gzwzm06
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
::
1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
<
2024年11月
>
日
一
二
三
四
五
六
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
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(3)
给我留言
查看公开留言
查看私人留言
随笔档案
2009年5月 (1)
文章分类
DP(12)
(rss)
Hash应用(4)
(rss)
几何(1)
(rss)
模拟题(2)
(rss)
数据结构(12)
(rss)
数学(2)
(rss)
搜索(2)
(rss)
图论(7)
(rss)
与Tree相关的题(2)
(rss)
字符串处理(8)
(rss)
文章档案
2009年5月 (8)
2009年4月 (5)
2009年3月 (14)
2008年11月 (20)
2008年10月 (5)
搜索
最新评论
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
巫
阅读(459)
评论(0)
编辑
收藏
引用
所属分类:
图论
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
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
知识库
博问
管理
Powered by:
C++博客
Copyright © 巫