• <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隨著中國經(jīng)濟(jì)的騰飛，中國的物流產(chǎn)業(yè)迎來了發(fā)展的春天。特別是在上海這樣一個(gè)擁有廣闊國內(nèi)腹地的國際化大都市，物流業(yè)以空前的速度膨脹。
              8當(dāng)然是大蛋糕就會(huì)吸引許多饞嘴貓，饞嘴貓多了就會(huì)有殘酷的競爭。當(dāng)大量資金流入物流產(chǎn)業(yè)時(shí)，KOP 集團(tuán)為了穩(wěn)坐在國內(nèi)物流業(yè)的第一把交椅，決定對(duì)現(xiàn)行的運(yùn)輸方案進(jìn)行改良，以減少自己的成本同時(shí)使其它競爭者知難而退。
              9作為世界100強(qiáng)的KOP集團(tuán)當(dāng)然知道要找到最優(yōu)運(yùn)輸方案，肯定得靠數(shù)學(xué)和算法很好的軟件工程師，于是他們理所當(dāng)然地找到華東師范大學(xué)軟件學(xué)院。決定通過贊助一場程序比賽來找出最優(yōu)秀的工程師( ACM : Ace Coding Man )。
             10比賽只有一道題目，是運(yùn)輸線路的簡單抽象，題意如下：
             11SH 市有N個(gè)運(yùn)輸中轉(zhuǎn)點(diǎn)(簡單標(biāo)示為 1,2,3,.,N)，中轉(zhuǎn)點(diǎn)之間可能有一條運(yùn)輸線路，這條線路有一個(gè)特殊的地方就是從A 到B點(diǎn)需要耗費(fèi) c1 個(gè)單位的查克拉(SH市的貨幣單位)，但從B到A可能需要 c2 個(gè)查克拉。當(dāng)然c1不一定等于c2，也能從A到B之后就不能從B返回A了。你可以理解為這些線路是“單向”的。線路總共有 M 條。每天有N-1輛車從KOP集團(tuán)總部(這里假設(shè)就是標(biāo)號(hào)為1的中轉(zhuǎn)點(diǎn))，出發(fā)，分別發(fā)往N-1個(gè)剩下的中轉(zhuǎn)點(diǎn)，然后當(dāng)天再從所到達(dá)的中轉(zhuǎn)點(diǎn)返回。你的任務(wù)就是要求出一天的最小耗費(fèi)。
             12
             13
             14----輸入：
             15
             16第一行為 C ，表示有C個(gè)測試用列。接下來分別為C個(gè)測試用列。
             17每個(gè)測試用例的格式如下：
             18第一行為兩個(gè)整數(shù)，N，M ,分別表示有N個(gè)中轉(zhuǎn)點(diǎn)和M條道路。( 1=< N, M <=1000000 .);
             19緊接著的M 行每行有三個(gè)值 A B c； 分別表示從中轉(zhuǎn)點(diǎn)A到中轉(zhuǎn)點(diǎn)B需要耗費(fèi) c 個(gè)單位的查克拉。 ( 0<= c <= 1000000000 ). 
             20
             21
             22----輸出：
             23
             24你的輸出應(yīng)該包括C行，每行輸出一個(gè)值，對(duì)應(yīng)于相應(yīng)的用列的最少耗費(fèi)。
             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) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久不见久久见免费影院www日本|
久久免费大片|
国产一区二区三区久久|
一本大道加勒比久久综合|
久久亚洲综合色一区二区三区|
久久久久人妻一区精品|
亚洲愉拍99热成人精品热久久|
av午夜福利一片免费看久久|
久久97久久97精品免视看|
亚洲va国产va天堂va久久|
精品国产婷婷久久久|
久久亚洲中文字幕精品有坂深雪|
久久黄视频|
久久精品嫩草影院|
一本色道久久88综合日韩精品|
久久精品国产亚洲一区二区|
久久香综合精品久久伊人|
97久久精品人人澡人人爽|
久久久久波多野结衣高潮|
久久久久成人精品无码
|
久久成人精品|
国产综合久久久久|
久久综合九色综合网站|
久久久久亚洲精品天堂久久久久久
|
午夜肉伦伦影院久久精品免费看国产一区二区三区
|
久久99精品国产麻豆宅宅|
A级毛片无码久久精品免费|
久久国产精品一国产精品金尊|
久久91精品国产91久|
亚洲婷婷国产精品电影人久久|
丁香久久婷婷国产午夜视频|
精品九九久久国内精品|
久久99精品久久久久婷婷|
青青草原精品99久久精品66|
久久无码中文字幕东京热|
免费精品国产日韩热久久|
午夜精品久久久久久久无码|
欧美激情精品久久久久久久九九九|
国产精品伊人久久伊人电影
|
午夜精品久久久久久毛片|
久久无码AV一区二区三区|