• <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)  編輯 收藏 引用  所屬分類: 圖論 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



亚洲精品国产成人99久久|
日本精品久久久久久久久免费|
亚洲国产精品高清久久久|
国内精品九九久久久精品|
国产成人精品久久|
久久精品国产男包|
97久久精品国产精品青草|
久久青青国产|
久久精品国产一区二区三区日韩|
久久久精品无码专区不卡|
麻豆一区二区99久久久久|
久久久久国产精品嫩草影院|
久久国产乱子伦免费精品|
久久久久亚洲AV无码专区桃色
|
思思久久99热只有频精品66|
国产午夜福利精品久久2021
|
一级做a爰片久久毛片免费陪|
久久99国产综合精品女同|
亚洲精品综合久久|
久久91精品国产91久久麻豆|
久久精品国产久精国产果冻传媒|
久久精品国产一区二区三区不卡|
亚洲va国产va天堂va久久|
色婷婷久久久SWAG精品|
91久久精品无码一区二区毛片|
久久婷婷国产综合精品|
久久久久久精品成人免费图片|
久久人人爽人人爽AV片|
情人伊人久久综合亚洲|
狠狠色丁香久久婷婷综合五月|
77777亚洲午夜久久多喷|
亚洲欧美成人久久综合中文网|
久久播电影网|
久久高清一级毛片|
国内精品免费久久影院|
久久国产成人亚洲精品影院|
亚洲午夜久久影院|
99久久国产综合精品五月天喷水
|
国产成人精品久久二区二区|
久久国产精品99精品国产|
青青草原精品99久久精品66|