• <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>
            

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			EOJ 1848 你是ACM嗎？
		
            
		
              1/*
              2EOJ 1848 你是ACM嗎？
              3
              4
              5----問題描述：
              6
              7隨著中國經濟的騰飛，中國的物流產業迎來了發展的春天。特別是在上海這樣一個擁有廣闊國內腹地的國際化大都市，物流業以空前的速度膨脹。
              8當然是大蛋糕就會吸引許多饞嘴貓，饞嘴貓多了就會有殘酷的競爭。當大量資金流入物流產業時，KOP 集團為了穩坐在國內物流業的第一把交椅，決定對現行的運輸方案進行改良，以減少自己的成本同時使其它競爭者知難而退。
              9作為世界100強的KOP集團當然知道要找到最優運輸方案，肯定得靠數學和算法很好的軟件工程師，于是他們理所當然地找到華東師范大學軟件學院。決定通過贊助一場程序比賽來找出最優秀的工程師( ACM : Ace Coding Man )。
             10比賽只有一道題目，是運輸線路的簡單抽象，題意如下：
             11SH 市有N個運輸中轉點(簡單標示為 1,2,3,.,N)，中轉點之間可能有一條運輸線路，這條線路有一個特殊的地方就是從A 到B點需要耗費 c1 個單位的查克拉(SH市的貨幣單位)，但從B到A可能需要 c2 個查克拉。當然c1不一定等于c2，也能從A到B之后就不能從B返回A了。你可以理解為這些線路是“單向”的。線路總共有 M 條。每天有N-1輛車從KOP集團總部(這里假設就是標號為1的中轉點)，出發，分別發往N-1個剩下的中轉點，然后當天再從所到達的中轉點返回。你的任務就是要求出一天的最小耗費。
             12
             13
             14----輸入：
             15
             16第一行為 C ，表示有C個測試用列。接下來分別為C個測試用列。
             17每個測試用例的格式如下：
             18第一行為兩個整數，N，M ,分別表示有N個中轉點和M條道路。( 1=< N, M <=1000000 .);
             19緊接著的M 行每行有三個值 A B c； 分別表示從中轉點A到中轉點B需要耗費 c 個單位的查克拉。 ( 0<= c <= 1000000000 ). 
             20
             21
             22----輸出：
             23
             24你的輸出應該包括C行，每行輸出一個值，對應于相應的用列的最少耗費。
             25
             26
             27----樣例輸入：
             28
             292
             302 2
             311 2 13
             322 1 33
             334 6
             341 2 10
             352 1 60
             361 3 20
             373 4 10
             382 4 5
             394 1 50
             40
             41
             42----樣例輸出：
             43
             4446
             45210
             46
             47
             48----分析：
             49
             50*/
             51
             52
             53#include <stdio.h>
             54#include <string.h>
             55
             56#define  N  1000009
             57#define  M  2000009
             58
             59typedef __int64 Tint;
             60
             61typedef struct __EDGE
             62{
             63        int v, w;
             64        struct __EDGE *next;
             65}             EDGE;
             66
             67EDGE MemEdgeSpace[ M ];
             68int  MemEdgeTop;
             69#define MemEdgeInit() MemEdgeTop = 0
             70#define MemEdgeNew()  ( MemEdgeSpace + MemEdgeTop++ )
             71
             72typedef struct
             73{
             74        EDGE *edgeHead, *edgeTail;
             75}             NODE;
             76
             77NODE v1[ N ], v2[ N ];
             78
             79Tint Spfa( NODE * v, int n ){
             80#define OO ( 2123456789i64 * 2123456789i64 )
             81        static int  q[ N ], qh, qt, inq[ N ], s, i, j;
             82        static Tint dist[ N ], tot;
             83        static EDGE *p;
             84        qh = 0;
             85        qt = 1;
             86        q[ 0 ] = 1;
             87        memset( inq + 1, 0, sizeof(inq[0]) * n );
             88        inq[ 1 ] = 1;
             89        for( i = n; i > 0; --i ){
             90                dist[ i ] = OO;
             91        }
             92        dist[ 1 ] = 0;
             93        while( qh != qt ){
             94                s = q[ qh ];
             95                inq[ s ] = 0;
             96                qh = ( qh + 1 ) % N;
             97                for( p = v[ s ].edgeHead; p; p = p->next ){
             98                        if( dist[ s ] + p->w < dist[ j = p->v ] ){
             99                                dist[ j ] = dist[ s ] + p->w;
            100                                if( ! inq[ j ] ){
            101                                        q[ qt ] = j;
            102                                        inq[ j ] = 1;
            103                                        qt = ( qt + 1 ) % N;
            104                                }
            105                        }
            106                }
            107        }
            108
            109        tot = dist[ 1 ];
            110        for( i = n; i > 1; --i ){
            111                tot += dist[ i ];
            112        }
            113        return tot;
            114#undef OO
            115}
            116
            117int main(){
            118        int i, j, k, n, m, td;
            119        EDGE *p;
            120        scanf( "%d", &td );
            121        while( td-- ){
            122                scanf( "%d%d", &n, &m );
            123                memset( v1 + 1, 0, sizeof(v1[0]) * n );
            124                memset( v2 + 1, 0, sizeof(v2[0]) * n );
            125                MemEdgeInit();
            126                while( m-- ){
            127                        scanf( "%d%d%d", &i, &j, &k );
            128                        #define ADD_EDGE(va,i,j,k) \
            129                        p = MemEdgeNew(); 
            130                        p->v = j; 
            131                        p->w = k; 
            132                        p->next = 0; 
            133                        if( va[ i ].edgeHead ){ 
            134                                va[ i ].edgeTail->next = p; 
            135                                va[ i ].edgeTail = p; 
            136                        }             
            137                        else{ 
            138                                va[ i ].edgeHead = va[ i ].edgeTail = p; 
            139                        }
            140                        ADD_EDGE( v1, i, j, k );
            141                        ADD_EDGE( v2, j, i, k );
            142                        #undef ADD_EDGE
            143                }
            144                printf( "%I64d\n", Spfa( v1, n ) + Spfa( v2, n ) );
            145        }
            146        return 0;
            147}
            148
            
		
            
			posted on 2012-05-14 16:12 coreBugZJ 閱讀(683) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



女人香蕉久久**毛片精品|
久久午夜无码鲁丝片午夜精品|
无码超乳爆乳中文字幕久久|
五月丁香综合激情六月久久|
99久久精品毛片免费播放|
26uuu久久五月天|
久久99久国产麻精品66|
国产精品久久网|
99久久这里只精品国产免费|
97久久精品无码一区二区|
久久久久亚洲精品无码网址|
久久无码高潮喷水|
久久99国产精品久久99果冻传媒
|
久久久久久精品无码人妻|
久久人人爽人人爽人人片av高请|
97精品国产97久久久久久免费|
中文国产成人精品久久不卡|
99久久婷婷国产综合精品草原|
久久久久国产精品嫩草影院|
久久久WWW成人免费毛片|
久久精品国产亚洲AV香蕉|
一本久久综合亚洲鲁鲁五月天|
四虎国产精品免费久久5151|
中文精品久久久久人妻不卡|
性做久久久久久久久老女人|
97精品伊人久久久大香线蕉|
国产精品一区二区久久|
久久人人爽人人爽人人片AV不
|
精品久久人人爽天天玩人人妻|
丁香色欲久久久久久综合网|
色综合久久久久综合99|
国产精品熟女福利久久AV
|
国产精品青草久久久久福利99|
色偷偷久久一区二区三区|
久久国产精品99久久久久久老狼|
久久影院久久香蕉国产线看观看|
久久99热狠狠色精品一区|
av无码久久久久不卡免费网站|
伊人久久大香线蕉综合Av|
久久久噜噜噜久久中文字幕色伊伊
|
9久久9久久精品|