• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
              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 巫 閱讀(466) 評論(0)  編輯 收藏 引用  所屬分類: 圖論 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



青青草国产精品久久|
久久人妻少妇嫩草AV蜜桃|
久久精品免费大片国产大片|
91精品国产高清久久久久久io|
欧洲精品久久久av无码电影|
一本久久精品一区二区|
中文字幕无码久久精品青草
|
欧美精品福利视频一区二区三区久久久精品
|
久久福利青草精品资源站|
99久久免费国产精精品|
久久精品国产亚洲av麻豆色欲|
久久人人爽人人爽人人片AV不
|
国产99久久久久久免费看|
青青草原综合久久大伊人精品|
精品久久久久久国产牛牛app|
精品久久久久久无码中文野结衣|
久久精品国产精品亚洲下载|
欧美久久久久久午夜精品|
久久国产亚洲精品|
欧美精品久久久久久久自慰|
99久久国产综合精品麻豆|
国产福利电影一区二区三区久久久久成人精品综合
|
久久精品人人做人人妻人人玩|
国产精品久久久久久久久免费|
久久91精品久久91综合|
久久国产免费直播|
久久精品桃花综合|
精品久久久久久国产潘金莲|
久久91精品综合国产首页|
久久精品aⅴ无码中文字字幕不卡|
国产精品久久午夜夜伦鲁鲁|
999久久久免费国产精品播放|
久久午夜无码鲁丝片秋霞|
久久综合九色综合精品|
久久人妻AV中文字幕|
亚洲乱亚洲乱淫久久|
亚洲精品无码久久久久sm|
曰曰摸天天摸人人看久久久|
少妇久久久久久久久久|
久久亚洲欧洲国产综合|
国产三级久久久精品麻豆三级|