gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 1511(Dij + Heap)
  1#include <stdio.h>
  2#include <cstring>
  3
  4const int MAXN = 10001001 ;
  5const __int64 INT_MAX = 2000000000 ;
  6
  7
  8//edge 原图 redge 反图
  9//用反图求Dij，就可算出其他点到源点的最短路径(非常有用)
 10struct EDGE
 11{
 12    int ID ;
 13    __int64 wg ;
 14    struct EDGE *next ;
 15}edge[MAXN], redge[MAXN], g_Temp[MAXN * 2] ;
 16
 17int g_Level = 0 ;
 18
 19int V , E ;
 20__int64 weight[MAXN] ;
 21__int64 ecost[MAXN] ;
 22bool visited[MAXN] ;
 23
 24struct 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
 37int g_Htail ;
 38
 39inline 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
 64inline 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
102void 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
162void 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
175inline 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
190int 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 巫 阅读(445) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理