• <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)  編輯 收藏 引用 所屬分類: 圖論
            99久久精品国产综合一区 | 亚洲精品无码久久一线| 亚洲国产成人乱码精品女人久久久不卡| 99久久精品无码一区二区毛片| 久久夜色精品国产www| 人妻无码αv中文字幕久久琪琪布| 日本久久久精品中文字幕| 无码8090精品久久一区| 久久棈精品久久久久久噜噜| 99热都是精品久久久久久| 7777久久久国产精品消防器材| 亚洲嫩草影院久久精品| 少妇久久久久久被弄高潮| 欧美伊人久久大香线蕉综合69| 久久精品亚洲日本波多野结衣| 久久精品亚洲精品国产欧美| 久久大香香蕉国产| 久久精品中文字幕一区| 久久99精品久久久久久9蜜桃| 久久久久亚洲AV片无码下载蜜桃| 国产综合免费精品久久久| 久久久久亚洲av无码专区| 亚洲日韩中文无码久久| 热久久国产欧美一区二区精品| …久久精品99久久香蕉国产| 亚洲精品乱码久久久久久| 久久精品亚洲AV久久久无码| 亚洲精品tv久久久久| 日韩亚洲国产综合久久久| 久久精品二区| 手机看片久久高清国产日韩| 99久久国产免费福利| 国产精品成人99久久久久| 国产亚洲成人久久| 久久av免费天堂小草播放| 精品久久综合1区2区3区激情| 国产成人精品久久亚洲高清不卡| 久久99精品国产一区二区三区 | 久久久久久免费视频| 欧美精品乱码99久久蜜桃| 久久久久亚洲国产|