国产精品久久久久久搜索,内射无码专区久久亚洲,亚洲精品久久久www

POJ 3268(最短路徑 SPFA)

跟POJ 1511一樣

#include <cstdio>
2

#include <cstring>
3

const int MAXN = 101000 ;
5

const int INT_MAX = 2000000 ;
6

struct NODE
8

{
9

int v ;
10

int w ;
11

NODE *next ;
12

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

int g_Pos = 0 ;
15

int ecost[MAXN] ;
17

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

bool visited[MAXN] ;
20

bool SPFA(bool rg = false)
22

{
23

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

NODE *ptr ;
25

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

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

ecost[i] = INT_MAX ;
30

Q[0] = src ;
32

ecost[src] = 0 ;
34

while ( h != t )
36

{
37

u = Q[h] ;
38

h++ ;
39

visited[u] = false ;
41

if ( !rg )
43

ptr = edge[u].next ;
44

else
45

ptr = redge[u].next ;
46

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

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

}
64

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

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

void Init()
81

{
82

g_Pos = 0 ;
83

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

{
86

edge[i].next = NULL ;
87

redge[i].next = NULL ;
88

}
89

}
90

int main()
92

{
93

int i , x , y , w ;
94

int ans[MAXN] , MaxTime ;
95

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 巫閱讀(915) 評論(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 博問 Chat2DB 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論