• <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++博客 ::
首頁 ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				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，就可算出其他點(diǎn)到源點(diǎn)的最短路徑(非常有用)
             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到其他點(diǎn)的最短路徑
            212        HeapDij( 1, V ) ;
            213        
            214        for ( j = 2 ; j <= V ; ++j )
            215            ans += ecost[j] ;
            216
            217        //在求其他點(diǎn)到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 巫 閱讀(474) 評論(0)  編輯 收藏 引用  所屬分類: 圖論 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久精品成人免费网站|
久久激情五月丁香伊人|
精品国产乱码久久久久久郑州公司|
一本色道久久88精品综合|
久久久久久久99精品免费观看|
久久99精品国产99久久6|
久久无码高潮喷水|
国产91久久精品一区二区|
久久久久99精品成人片三人毛片
|
国产一区二区三精品久久久无广告|
久久亚洲国产精品123区|
99热成人精品热久久669|
久久久久亚洲av综合波多野结衣|
国产福利电影一区二区三区久久久久成人精品综合
|
精品国产福利久久久|
久久无码中文字幕东京热|
国产免费久久精品99久久|
性色欲网站人妻丰满中文久久不卡|
久久国产精品一区|
亚洲国产精品久久久久婷婷软件|
无码AV波多野结衣久久|
伊人久久无码精品中文字幕|
国产免费久久精品99久久|
亚洲国产精品久久久久婷婷软件|
久久久久亚洲精品无码蜜桃|
香蕉久久av一区二区三区|
狠狠色婷婷久久一区二区
|
人人狠狠综合久久88成人|
东方aⅴ免费观看久久av|
无码人妻久久一区二区三区蜜桃|
亚洲国产成人久久精品99|
久久香蕉国产线看观看猫咪?v|
伊人色综合久久天天|
伊人久久大香线焦综合四虎
|
国产一区二区久久久|
亚洲国产精品无码久久青草|
久久性精品|
亚洲国产欧洲综合997久久|
久久久久久久久久久久中文字幕|
色综合久久久久无码专区|
国产人久久人人人人爽
|