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





            
	    
    




            






            

				

            


    
    







            
	   
	



精品国产91久久久久久久a|
久久99久久无码毛片一区二区|
亚洲精品无码专区久久同性男|
亚洲国产婷婷香蕉久久久久久|
久久99精品国产麻豆宅宅|
色欲久久久天天天综合网精品|
丁香五月网久久综合|
亚洲精品国产自在久久|
精品久久8x国产免费观看|
久久婷婷色综合一区二区|
久久久青草青青国产亚洲免观|
久久人人爽人人爽人人片AV高清|
99久久99这里只有免费费精品|
国产午夜福利精品久久|
国内精品久久久久久99|
亚洲精品97久久中文字幕无码|
国产精品99久久精品|
精品久久人人爽天天玩人人妻|
婷婷久久综合九色综合98|
久久无码AV中文出轨人妻|
国产ww久久久久久久久久|
精品蜜臀久久久久99网站|
中文字幕无码精品亚洲资源网久久|
久久国产精品免费|
国产成人久久精品二区三区|
1000部精品久久久久久久久|
精品国产乱码久久久久久呢|
久久久精品久久久久影院|
久久精品免费网站网|
狠狠人妻久久久久久综合|
丰满少妇人妻久久久久久4|
久久91精品国产91久久户|
亚洲AV无码久久寂寞少妇|
亚洲精品tv久久久久久久久|
久久久亚洲AV波多野结衣|
久久综合色老色|
久久人妻AV中文字幕|
久久香蕉国产线看观看精品yw|
人妻无码精品久久亚瑟影视|
伊人久久大香线蕉亚洲|
伊人久久大香线蕉av不卡|