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 阅读(673) 评论(0)  编辑 收藏 引用 所属分类: ACM 、Algorithm 、课内作业


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