Posted on 2008-09-05 19:28
Hero 閱讀(189)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1511 Accepted 196124K 4141MS C++ 4292B PKU
2
3 //堆優化的鄰接鏈表形式的最短路徑
4 //注意Heap_Dijkstra( 1, 0 )而不是(1, inn)
5
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9
10
11 const int size = 1010010 ;
12 const long long INF = 10000000000000 ;
13
14 struct NODE
15 {
16 int num ;
17 long long len ;
18 struct NODE *next ;
19
20 //NODE() { len = INF ; next = NULL ; }
21 };
22 //struct NODE head[size*90] ;
23 struct NODE head1[size*10] ;
24 struct NODE head2[size*10] ;
25 int chead ;
26
27 struct EDGE
28 {
29 int sn ; int en ; long long len ; int toheap ;
30 };
31 struct EDGE dist1[size] ;
32 struct EDGE dist2[size] ;
33 //typedef struct EDGE EDGE ;
34
35 int flag[size] ;
36 int heap[size] ; int numh ;
37
38 int inn, inm ; int innum ;
39 long long out ;
40
41 void input()
42 {
43 for( int i=0; i<=inn; i++ ) head1[i].next = head2[i].next = NULL ;
44
45 int sn, en, len ; chead = inn + 10 ; struct NODE *temp ;
46 for( int i=1; i<=inm; i++ )
47 {
48 scanf( "%d %d %d", &sn, &en, &len ) ;
49 //data[i][0] = sn ; data[i][1] = en ; data[i][2] = len ;
50 //temp = (struct NODE *)malloc( sizeof(NODE) ) ;
51 //struct NODE *temp = new NODE ;
52 temp = &head1[chead++] ;
53 temp->len = len ; temp->num = en ;
54 temp->next = head1[sn].next ; head1[sn].next = temp ;
55
56 //temp = (struct NODE *)malloc( sizeof(NODE) ) ;
57 temp = &head2[chead++] ;
58 temp->len = len ; temp->num = sn ;
59 temp->next = head2[en].next ; head2[en].next = temp ;
60 }
61 }
62
63 void swap( int &a, int &b )
64 {
65 int t = a ; a = b ; b = t ;
66 }
67
68 void moveup( EDGE *arry, int n )
69 {//將新加入的節點向上移動來維持堆,n表示要向上移動的點的坐標
70 //while( n && arry[n] > arry[(n-1)>>1] )//大頂堆
71 while( n&&arry[heap[n]].len<arry[heap[(n-1)/2]].len )//小頂堆
72 {
73 swap( arry[heap[n]].toheap, arry[heap[(n-1)/2]].toheap ) ;
74 swap( heap[n], heap[(n-1)/2] ) ;
75 n = (n-1) / 2 ;
76 }
77 }
78
79 void movedown( EDGE *arry, int n )
80 {//堆頂改變后,將其向下移動維持堆,n表示堆中元素總數目
81 int i = 0 ;
82 while( i+i+1 < n )
83 {
84 //if( i+i+2<n&&arry[i+i+2]>arry[i+i+1]&&arry[i+i+2]>arry[i] )
85 if( i+i+2<n&&arry[heap[i+i+2]].len<arry[heap[i+i+1]].len&&arry[heap[i+i+2]].len<arry[heap[i]].len )
86 {
87 swap( arry[heap[i+i+2]].toheap, arry[heap[i]].toheap ) ;
88 swap( heap[i+i+2], heap[i] ) ;
89 i = i + i + 2 ;
90 }
91 //else if( arry[i+i+1] > arry[i] )
92 else if( arry[heap[i+i+1]].len < arry[heap[i]].len )
93 {
94 swap( arry[heap[i+i+1]].toheap, arry[heap[i]].toheap ) ;
95 swap( heap[i+i+1], heap[i] ) ;
96 i = i + i + 1 ;
97 }
98 else break ;
99 }
100
101 }
102
103 void Heap_Dijkstra( EDGE dist[], NODE head[], int sn, int en )
104 {
105 numh = -1 ; struct NODE * p ;
106 for( int i=1; i<=inn; i++ )
107 {
108 if( i == sn )
109 {
110 flag[i] = 1 ; //pren[i] = -1 ;
111 dist[i].sn = sn ; dist[i].en = sn ; dist[i].len = 0 ;
112 heap[++numh] = i ; dist[i].toheap = numh ; moveup( dist, numh ) ;
113 }
114 else
115 {
116 flag[i] = 0 ; //pren[i] = sn ;
117 dist[i].sn = sn ; dist[i].en = i ;
118 //for( p=head[sn].next; p!=NULL&&p->num!=i; p=p->next ) ;
119 //if( NULL == p ) dist[i].len = INF ; else dist[i].len = p->len ;
120 dist[i].len = INF ;
121 heap[++numh] = i ; dist[i].toheap = numh ; moveup( dist, numh ) ;
122 }
123 }//init
124 for( int ct=1; ct<=inn; ct++ )
125 {
126 if( numh < 0 ) break ;
127 int next = dist[heap[0]].en ; if( dist[next].len >= INF ) break ;
128 if( next == en ) return ;
129 swap( dist[heap[0]].toheap, dist[heap[numh]].toheap ) ;
130 swap( heap[0], heap[numh] ) ; numh-- ; movedown( dist, numh+1 ) ;
131 flag[next] = 1 ; int curn ;
132 for( p=head[next].next; p; p=p->next )
133 {
134 curn = p->num ;
135 if( 0==flag[curn]&&p->len<INF&&dist[next].len+p->len<dist[curn].len )
136 {
137 dist[curn].len = dist[next].len + p->len ; //pren[curn] = next ;
138 moveup( dist, dist[curn].toheap ) ;
139 }
140 }
141 }
142 }
143
144 void process()
145 {
146 out = 0 ;
147
148 Heap_Dijkstra( dist1, head1, 1, 0 ) ;
149 for( int i=1; i<=inn; i++ ) out += dist1[i].len ;
150
151 Heap_Dijkstra( dist2, head2, 1, 0 ) ;
152 for( int i=1; i<=inn; i++ ) out += dist2[i].len ;
153 }
154
155 void output()
156 {
157 printf( "%lld\n", out ) ;
158 }
159
160 int main()
161 {
162 //freopen( "in.txt", "r", stdin ) ;
163 //freopen( "out.txt", "w", stdout ) ;
164
165 //while( scanf( "%d", &innum ) != EOF )
166 scanf( "%d", &innum ) ;
167 {
168 for( int ct=1; ct<=innum; ct++ )
169 {
170 scanf( "%d %d",&inn, &inm ) ;
171
172 input() ;
173
174 process() ;
175
176 output() ;
177 }
178 }
179
180 return 0 ;
181 }