• <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 閱讀(702) 評論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內作業 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



香蕉久久夜色精品升级完成|
亚洲AV无一区二区三区久久|
国产99久久久久久免费看|
久久影院久久香蕉国产线看观看|
亚洲国产精品狼友中文久久久|
国内高清久久久久久|
国内精品久久久久影院网站|
久久青青色综合|
久久精品国产AV一区二区三区|
国产精品青草久久久久婷婷|
久久久国产99久久国产一|
久久777国产线看观看精品|
一本一本久久a久久精品综合麻豆|
久久成人国产精品二三区|
久久精品国产日本波多野结衣
|
亚洲精品高清国产一线久久|
99热成人精品免费久久|
久久超碰97人人做人人爱|
亚洲国产成人久久综合一区77|
久久香蕉一级毛片|
久久66热人妻偷产精品9|
精品熟女少妇AV免费久久|
久久久久亚洲av成人无码电影|
国产A级毛片久久久精品毛片|
国产精品一久久香蕉国产线看观看|
久久99这里只有精品国产|
久久久久久国产精品无码下载|
91亚洲国产成人久久精品网址|
免费国产99久久久香蕉|
91精品免费久久久久久久久|
国产精品天天影视久久综合网|
久久久免费精品re6|
国产精品伦理久久久久久|
老司机国内精品久久久久|
久久精品视频网|
97精品国产97久久久久久免费|
精品久久久久久久久中文字幕|
久久国产高清字幕中文|
久久精品国产99国产精偷|
国产精品成人无码久久久久久
|
久久香综合精品久久伊人|