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 3268(最短路徑 SPFA)

跟POJ 1511一樣

1

#include <cstdio>
2

#include <cstring>
3

4

const int MAXN = 101000 ;
5

const int INT_MAX = 2000000 ;
6

7

struct NODE
8

{
9

int v ;
10

int w ;
11

NODE *next ;
12

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

14

int g_Pos = 0 ;
15

16

int ecost[MAXN] ;
17

int N , M , W , src , Q[MAXN];
18

19

bool visited[MAXN] ;
20

21

bool SPFA(bool rg = false)
22

{
23

int h = 0 , t = 1 , u ;
24

NODE *ptr ;
25

26

memset(visited, 0, sizeof(visited)) ;
27

28

for ( int i = 0 ; i <= N ; ++i )
29

ecost[i] = INT_MAX ;
30

31

Q[0] = src ;
32

33

ecost[src] = 0 ;
34

35

while ( h != t )
36

{
37

u = Q[h] ;
38

h++ ;
39

40

visited[u] = false ;
41

42

if ( !rg )
43

ptr = edge[u].next ;
44

else
45

ptr = redge[u].next ;
46

47

while ( ptr ){
48

if ( ecost[ptr->v] > ecost[u] + ptr->w ) //松弛操作
49

{
50

ecost[ptr->v] = ecost[u] + ptr->w ;
51

if ( !visited[ptr->v] )
52

{
53

Q[t] = ptr->v ;
54

t++ ;
55

visited[ptr->v] = true ;
56

}
57

}
58

ptr = ptr->next ;
59

}
60

}
61

62

return ( ecost[N] != INT_MAX ) ;
63

}
64

65

void Insert( const int& x, const int& y, const int& w )
66

{
67

NODE *ptr = &g_Temp[g_Pos++] ;
68

ptr->v = y ;
69

ptr->w = w ;
70

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

edge[x].next = ptr ;
72

73

ptr = &g_Temp[g_Pos++] ;
74

ptr->v = x ;
75

ptr->w = w ;
76

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

redge[y].next = ptr ;
78

}
79

80

void Init()
81

{
82

g_Pos = 0 ;
83

84

for ( int i = 0 ; i <= N ; ++i )
85

{
86

edge[i].next = NULL ;
87

redge[i].next = NULL ;
88

}
89

}
90

91

int main()
92

{
93

int i , x , y , w ;
94

int ans[MAXN] , MaxTime ;
95

96

while ( scanf("%d %d %d", &N, &M, &src) != EOF )
97

{
98

Init() ;
99

for ( i = 0 ; i < M ; ++i )
100

{
101

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

Insert( x, y, w ) ;
103

}
104

105

MaxTime = 0 ;
106

memset(ans, 0, sizeof(ans)) ;
107

108

//照樣對正反圖求最短路
109

SPFA() ;
110

111

for ( i = 1 ; i <= N ; ++i )
112

{
113

if ( i != src )
114

ans[i] += ecost[i] ;
115

}
116

117

SPFA( true ) ;
118

119

for ( i = 1 ; i <= N ; ++i )
120

if ( i != src )
121

{
122

ans[i] += ecost[i] ;
123

if ( ans[i] > MaxTime )
124

MaxTime = ans[i] ;
125

}
126

127

printf("%d\n", MaxTime) ;
128

}
129

130

return 0 ;
131

}

posted on 2008-11-20 13:03 巫閱讀(927) 評論(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 管理

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