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 + 10sizeof(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->< 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 + 10sizeof(v1[0]) * n );
124                memset( v2 + 10sizeof(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->= j; 
131                        p->= 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 阅读(663) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithm课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理